Actually, an improvement on the last suggestion.

Determine an acceptable (given technology) rate of growth of the total set of unspent outputs. Every 2 weeks, adjust the number of (new unspent outputs created - previous unspent outputs spent) allowed per block, based on how closely the maximum rate of growth is being tracked.

This makes the size of all unspent outputs a resource that is subject to an economic feedback loop, just as we already have (in theory) with the total size of each block. That minimizes transaction fees without ruling out legitimate transactions that look like dust (micropayments).

Miners could pay users to spend lots of dust outputs, since it allows them to include more unspent outputs (which they can charge for) in their block.