Without any changes to the protocol itself miners could make it economical to create transactions which reduce the UTXO set by changing their transaction rules to favor transactions which reduce dust. Once this happens, clients could be programmed to do that automatically.
One way it could be done: if all outputs are above the dust cutoff, and if N inputs are below the dust cutoff, prioritize the transaction as if it included N*the minimum fee in addition to fees which are actually present.
One way it could be done: if all outputs are above the dust cutoff, and if N inputs are below the dust cutoff, prioritize the transaction as if it included N*the minimum fee in addition to fees which are actually present.
I don't think the BTC-size of the inputs should matter. Simply look at whether it increases or reduces the global UTXO set all full nodes will have to track. Even huge transactions should be free if they combine dozens of inputs into a one or two outputs. As long as it is very expensive to go the other way.
In fact, you could look at the contraction efficiency of a transaction: how many kB did it use to remove X UTXOs from the set? Above a certain efficiency, those tx should be free. Any neutral or negative tx will be charged a fee, with the highest fees going to those who dramatically expand the set. But the rules should be balanced so that it's not cheaper to send 100 single-output transactions instead of a single 100-output tx.
Your reasoning would make sense to me if UTXO set size was the only scarce resource being rationed, but block space needs to be rationed at the same time. This means transaction priority can't be coin value-agnostic.
Edit: Additionally, the UTXO set size is naturally bounded if uneconomical coin values are discouraged. Of course this brings up the problem of discouraging exotic uses of small valued coins. I addressed this here though if you're interested: https://bitcointalksearch.org/topic/discouraging-dust-without-hurting-exotic-uses-of-small-valued-coins-151177.
