How about a solution like this. A transaction can include outputs that anyone can spend, without requiring a private key to unlock; let's call them "free" outputs. So, the smaller any single output is, the more free outputs the transaction must have, with each free output equal to the standard transaction fee.
Obviously the free outputs will be claimed by clients that relay or mine the transaction. Some clients might not relay the transaction if all the free outputs are already taken, therefore in the interest of propogation, a single relaying client will not be tempted to immediately claim all the free transactions.
However -- I'm not sure about a technical aspect of this. Suppose I send a transaction with two free outputs. The first relay claims one and leaves another blank. The transaction is then mined, so the miner claims the second. However: could the miner also *erase* the claim on the first free output, and insert a new claim on it? In other words, can the original transaction be derived from the one in which the first free output is claimed?
An alternative solution is this. At the moment, the fee is TXFEE * TXSIZE, where TXFEE is 0.0005BTC and TXSIZE is measured in kB, right? And the fee must be applied if: a) the priority is low b) TXSIZE > 1 or c) any output < 0.01 BTC. How about changing the fee to: TXFEE*TXSIZE + SUM_{OUTPUTS<0.01}(TXFEE*log2(0.01/outputvalue)). Let me explain:
TXFEE*TXSIZE is the same as before.
0.01/outputvalue = 1.0 if outputvalue=0.01
= 2 if outputvalue=0.005
= 8 if outputvalue=0.000125
and so on.
log_2(...) = 0 if outputvalue=0.01
= 1 if outputvalue=0.005
= 3 if outputvalue=0.000125
and so on
So, for each output below 0.01BTC (threshold which depends on bitcoin value, currently ~$40), every time the output halves in value, the transaction fee must increase by TXFEE.
So, a 750Byte transaction with outputs (0.5, 0.01, 0.009, 0.001, 0.00000001) will require a fee on the last three outputs only: TXFEE*[log2(0.01/0.009) + log2(0.01/0.001) + log2(0.01/1e-8)] = TXFEE*[0.15 + 3.32 + 19.93] = 23.4 * TXFEE.
As you can see, the 1 satoshi output really costs alot of fees.
The problem is that this will merely make the transaction more expensive benefiting the miner - it will not reward non-miners for having to store, relay and validate the output (though that might be impossible anyway).