kinda reminds me of the nuclear waste debate. It's a future liability which is not captured by current transaction fees.

Would a simple change to the propagation rule fix this problem: ?

do not propagate if:
fee > unspent transaction output.

This would prevent satoshi-type unspent transaction outputs, unless they are introduced with zero fees. And those should be filtered out heavily in a transaction fee governed market. (Although such a rule would probably have collateral damage for other valid transaction models, e.g. colored coins)