For all blocks where block.number >= FORK_BLKNUM (TBA):
The cases where a "touch" takes place can be enumerated as follows:
When the EVM checks for emptiness (for the purpose of possibly applying the 25000 gas cost), emptiness is defined by is_empty(acct): return get_balance(acct) == 0 and get_code(acct) == "" and get_nonce(acct) == 0; emptiness of storage does not matter. This simplifies client implementation because there is no need to add extra complexity to make caches enumerable in the correct way and does not significantly affect the intended result, as the cases where balance/code/nonce are empty but storage is nonempty where this change would lead to an extra 25000 gas being paid are pathological and have no real use value.
Do not implement point 2 above (ie. no new empty accounts can be created, but existing ones are not automatically destroyed unless their state is actually changed). Instead, during each block starting from (and including) N and ending when there are no null accounts left, select the 1000 null accounts that are left-most in order of sha3(address), and delete them (ordering by hash is necessary so as to allow the accounts to be easily found by iterating the tree).
This removes a large number of empty accounts that have been put in the state at very low cost due to flaws in earlier versions of the Ethereum protocol, thereby greatly reducing state size and hence both reducing the hard disk load of a full client and reducing the time for a fast sync. Additionally, it simplifies the protocol in the long term, as once all "empty" objects are cleared out there is no longer any meaningful distinction between an account being empty and being nonexistent, and indeed one can simply view nonexistence as a compact representation of emptiness.
Note that this proposal does introduce a temporary breaking of existing guarantees, in that by repeatedly zero-value-calling already existing empty accounts one can create a state change at a cost of 700 gas per account instead of the usual 5000 per gas minimum (with SUICIDE refunds this goes down further to 350 gas per account). Allowing such a large number of state writes per block will lead to heightened block processing times and increase uncle rates in the short term while the existing empty accounts are being cleared, and eventually once all empty accounts are cleared this issue will no longer exist.