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.
Thinking about this idea further, it's a great idea. It would probably work best if we add a tunable command line / config file parameter ranging from 0 to 1 where 0 gives us the current behavior (no prioritizing) and 1 gives us the full "N". Intermediate values would scale N down appropriately. Even better if 1 is the default. This way each miner could use the economic information available to them to decide how important dust collection is to their bottom line.
As I said before, too much SD toxic waste could accumulate in the block chain before sufficient miner action takes place but this is still a good change regardless because it provides the option to do something about it now for miners that don't mind sacrificing a small amount of potential fees, especially since there isn't enough legitimate transaction volume to fill a whole block anyway.
