I assume, given the recent state clearing, that the Ethereum clients must only store the current state of each account as opposed to all historic state. (Otherwise, if it stored a record of all past states for each account, wouldn't it still be storing the 20,000,000 empty accounts?)
But, if the clients only store the current state, how do they efficiently report on past balances as they do under this RPC call (https://github.com/ethereum/wiki/blob/master/JSON-RPC.md#eth_getbalance) which takes an optional block height?
Do the clients spin through the list of all transactions to build past balances or do the clients actually store past balances? If they store past balances, do they store any other history per account?