I think that, above all, we must maintain bitcoins decentralized nature. That means we should let miners price transactions.
At the end of the day, if a miner accepts a transaction in a block, he agrees to basically store it forever on his hardware. A transaction would therefore have a storage cost. It also has a computational cost as validation might be required in the future when spending outputs of this transaction.
Therefore, I strongly believe that, instead of finding static solutions to transaction costs, we must enable miners with tools to price them correctly. This is the only way we will see the light in a bumpy, uncertain and highly dynamic market environment. Good pricing competition should help us find an equilibrium.
If they don't do it already, miners need to start operating more like businesses. They need to crunch the number and understand the relationship between various transaction parameters and their cost. They need to do that for their own sake as they will need to host these transactions pretty much forever. They also need tools to tweak pricing quickly and dynamically as market forces change.
Under such assumptions, the current transaction dust we are experiencing should be reduced. My prediction is that if miners acted more as rational market players, they would require much higher fees for very small and young transactions. If the transaction is so small that it makes no economical sense to spend it, it should be priced accordingly. It will most likely be impossible to prune it and will require storage in UTXO memory. Some miners might also decide to drop them entirely. This is entirely up to them.
So how does the landscape look today? Are miners sufficiently empowered to dynamically change their pricing policies?