Thanks for producing this!
Priority queue
This seems like a substantial amount of protocol-layer complexity, and I disagree with the assertion that it “does not bring significant overhead”. One priority queue update is O(log(N)) but account state updates themselves are also O(log(N)), and the size of the priority queue and the existing account tree are both O(N); so it’s definitely a constant factor increase, and it seems like it could be a 1:1 factor.
Why not just allow a zero-gas transaction type that pokes up to N accounts to be deleted and then let miners add such a transaction to their blocks?
Regarding rent I’ll copy over a comment I made in another forum:
A third possibility that I have not yet seen discussed is to start off by raising the gas limit and increasing the SSTORE cost (possibly greatly increasing it, eg. 4-5x; also NOT increasing refunds to mitigate gastoken), and then start architecting a precompile that manages a cheaper class of temporary storage that follows some rent scheme.