Freshly pulled-out-of-the-air suggestion – anonymous but requiring micro-payments. Say, 500 or 1000 satoshi (around a tenth of a cent) per message delivered – not as a means of generating revenue, but as a way to destroy email's current "if I only get one sale per 100,000 emails I send, that just means I need to send 10,000,000 emails a day to get my desired 100sale/day" vulnerability - if that actually cost the spammer $10,000/day, it just wouldn't happen.

('course that required having hard currency to bitcoin exchanges easy enough for the general public to use, and scalable enough to service a significant proportion of internet-using people)