Update the email protocol so that all messages must be encrypted. Not "by default", but by necessity. The server rejects them if they aren't encrypted and signed in a way that proves the decryption key is on a block chain.
The only way to put the key in the chain is to submit a micro payment. By "courtesy" , but completely subject to the recipient, the users client will refund the payment 48 hrs after it has been decrypted/read. Only if they click "spam" then the payment stays on their ledger. This would kill spam overnight.
The two downsides I see so far are that the chain is a single point of failure for everyone, and it would cost people a few bucks and some friction to get the clients set up. Plus the coin would have to be very low transaction cost, and still fully redeemable for actual value somewhere.