What about this as a potential solution - in order to send an email to someone, you have to pay something.
Here's how it could work:
1) You sign up for a service that autoresponds to all incoming email stating that in order to send this receiver an email, they require at least X BTC.
2) The receivers inbox only shows email where the sender attached the minimum X BTC. In fact the inbox is sorted by the amount of BTC attached to each email.
3) The receiver keeps half the attached BTC and the email service keeps the other half. This is the part I'm least sure about.
Thoughts?