Another post (
https://bitcointalk.org/index.php?topic=128900.0) mentioned that currently 11% unspent output is 0.00000001BTC, 32% is less than 0.0001BTC and 60% is less than 0.001BTC. At the current price of US$13.5, 0.0001BTC worths only $0.00135. These are basically zero-value but take up 1/3 of resources of the network. To discourage these kinds of transaction, an even higher fee (e.g. 0.005BTC) should be charged with outputs < 0.0001BTC
Perhaps a dust threshold could be made dynamic based on the chain.
For example, compute the fee/KB for the last 2016 blocks and take its median value = MedianFee. Then assuming that every transaction must pay MedianFee/kb and each additional input to a transaction adds X bytes you arrive at a figure of MedianFee*X = the smallest output value which isn't worthless.
Unfortunately thin clients can't measure this value on their own, but its data they could reasonably just trust if their server provides it (lying results in a DOS attack, but a thinclients server can dos attack in many ways).
The proper thing to do with these transactions is not to relay or mine them at all since it appears that there is be no economic incentive to spend them. But this is a bit blunt as there are no doubt interesting ways to use small outputs which are not harmful, never redeemed bloat sources. I'm not sure how to best penalize these without completely denying them.