I need to update my suggestion. I have been told on IRC that the real problem is considered to be that unspent transaction outputs have to be stored in every fully validing node's memory. As opposed to the problem being total block chain size.

So my new suggestion is: Set a safe upper limit on the number of transaction outputs per block. Blocks with more outputs would be invalid and rejected by the network.

Advantages: Miners would optimize such that you need to pay a higher fee if you take up more of the unspent outputs in that block. Now, we let economic feedback kick in and we address the problem head on, rather than waiting for it to bite us as bitcoin usage grows and limiting dust transactions is not enough, since it only indirectly solves the problem.

Actually, you could do _both_ - set a safe upper limit on the block size to deal with storage issues and a safe upper limit on unspent outputs per block, too. Then you'd be totally safe.