Have a messaging system that implements per-MB fees in order to support the network. The transaction has to be signed by the sender, receiver, and burdened nodes. BOOM no spam.
Besides that, the idea is to attach two "stamps" to an encrypted message. One goes to the recipient and one goes to the mail server, but only in tandem. That pays the mail server for storing the message until the recipient goes online to pick it up. And it also stops people from running their own fake mail server that just skims stamps and throws away the messages. It's basically a throwaway dropbox.
I'm dreaming and have no idea how to implement it, but I've kicked it around for years ever since pondering the Your Idea Won't Work "form" (http://craphound.com/spamsolutions.txt)
Whether the result would be better that another unrelated product is irrelevant.
"here is a sugar-free pie !"
"you should add sugar to solve the sour taste problem"
"but, that would defeat the whole no-sugar thing ..."
"You must admit that it's still a lot less bad than soyent though !"