So I'm trying to figure out how to build this, and this is the idea that I've got:
Have 2 structures, one is the state, which tracks all the transactions and blocks, and the other is the consensus state, which tracks what the state of consensus is.
So the state keeps track of all the verified blocks, and all the not verified blocks, and puts them in a tree that somehow knows which is which. Then, as new transactions come in it keeps them in organized piles that are useful for figuring out consensus state.
Consensus state tracks two things: unspent outputs, and open contracts. From those two things you can arrive at consensus over the validity of every single transaction. We only keep one consensus state, and we keep it on the longest fork and that's it. We have a way to rewind it and build it up again, but we only do this if some other fork gets more work. If the fork ends up being invalid, (because some of the blocks included are invalid), we give up and go back to the original fork.
This means every block and transaction in the consensus state needs to be reversible. I don't think that this will be a difficult thing. It also means we're vulnerable to DoS attacks where constant forks force us to keep reversing long sets of blocks, figuring out a block is invalid, and then reversing the whole way back to the longest valid chain. Each time we do this though is expensive to the attacker, because they are doing enough work to create a block that is invalid. For the time being, I don't think that we need to worry about this attack vector.
The state needs to be in charge of reorganizing the ConsensusState, because only the state will be able to know which transactions are valid but haven't yet appeared in the current state. The state will need to keep track of all transactions, and will need to know which ones are potentially valid, and which ones won't be valid unless there's a reorg. But, it does need to keep track of transactions that become valid as the result of a reorg.
In short, no transaction is ever thrown away, no block is ever thrown away, and at any point the state knows what the current consensus is, and it knows from the list of every single transaction that it's ever seen what the complete list of potentially valid transactions are (potentially valid means they could go into a block and be confirmed without breaking any of the rules of consensus).