The fundamental problem is negative externalities.

The dust-spender doesn't pay the cost of the transaction.

There should be a default transaction cost that's a best-guess of the actual cost of a dust transaction.  Mining software should default to reject transactions with smaller fees.