Block size limit replaced by total block output size limit
The blockchain's size can be reduced drastically if the number of unspent outputs are reduced. Currently, the block size limit accomplishes this only indirectly. If this were replaced with a limit to block output size (say, at 500 kB), we would be targeting this directly.
Better would be to use number of outputs - number of inputs. That way miners might even pay for transactions with lots of inputs. I assume transactions with negative fees are not allowed atm?
Charge fees on outputs, not TX size
Really, for a transaction, nothing matters except the number of outputs. Outputs increase unprunable blockchain size. Combined with the block output size limit, this will shrink blockchain size considerably.
The network doesn't charge fees. You set your own fee, and the miner accepts it or not.
However, if the blocks were limited to a maximum UTXO set increase, then miners would naturally charge only for outputs.
- Uneconomic outputs solve themselves. If every output pays a fee, messaging transactions would become impractical. As fees change with price changes, the uneconomic line will move with them.
The fee is for a slot in the UTXO set. If that becomes really limited, users may demand merchants provide their own receiving UTXO.
- More anonymous. Instead of worrying about mixing inputs, the default client can maximize anonymity by using inputs that have not been connected to others, without extra fee.
If UTXO slots are inherently expensive, it encourages users to consolidate, so it reduces privacy.
Caveat
Of course, current inputs have not been paid for, so an implementation would have to start at a certain block. This solution would also seem to hardfork the blockchain. It would also require all inputs to be emptied with every transaction, but this happens already. The solution would make faucets and SatoshiDICE "you lose" messages uneconomic—but is that necessarily a bad thing?
You have the risk of UTXO set spam, if it looks like they are going to be expensive. People who split their money into loads of small holding would get more UTXO slots. However, the 1MB limit inherently limits the maximum UTXO set increase, but it could still expand. In the greater order of things that doesn't matter much.
Also, if you set a maximum number of outputs per block, then you hard limit the rate at which new users can enter the system.