Building off of that $0.000001 USD per email thing, has anyone proposed a proof of work per message sent system? Sort of like the server accepting messages says "hey find some value x where the first n digits of hash(nonce + x) are zero". So the server sending the message could decide if it really wants to complete the work.

It may be a total pain for users if servers set their proof of work really high and reject everything, but maybe it could be implemented to work well, thus limiting spam.

This would have the same effect as Gates's idea, but compute power is easier to come by than real money.