Require a small fee to send an email, e.g. $0.01. Small enough not to matter for legitimate users, large enough to make spam unprofitable.
Bitcoin or some other cryptocurrency would be ideal for facilitating micro-transactions like this. Interestingly, the Hashcash concept was originally designed to fight spam, and later became one of the important ideas that made the invention of Bitcoin possible: http://en.wikipedia.org/wiki/Hashcash
Right now I give out tagged addresses to most vendors, and I know others do it for lists. When a tag goes bad, I just route any further mail to my spam trainer.
But that means for every legitimate mailing list you're on, you get one spam. And you lose the legitimate mailing list just because their token got compromised.
Dunno, I feel like we should just charge for mailing lists too. Or use usenet!
If I can get it down to one spam each time a mailing list server is compromised, I'm ok with that.
Even with a charging scheme, some spam will still happen. Give the amount of BTC stolen so far, and given the number of compromised computers that could be used to generate cash, looks like there will be plenty of money to spend on sufficiently profitable spam.
I think the fee could be applied only to unsolicited emails. If I have a particular email address whitelisted then it will get through my gateway with no fee attached. However, if it is an unsolicited email from someone not on my whitelist it will be required to have some small fee attached to get past my filter.
I've seen some suggestions that instead of using money you could use some proof-of-work computation. This is something we could scale the difficulty factor of as computing power increased. Something that takes, say, an average computer 30 seconds (or longer) to calculate. It will attach this proof-of-work to the email.
Mailing lists wouldn't need to, or couldn't exist in this new magical email system. There's a hundred other solutions out there for what mailing lists provide.
Impose the fee only on one-way communications. A responsible mailing list would have a single instance of two-way communication when asking the user to confirm that they wanted to sign up. No I have no idea how that much state should be handled in a distributed fashion.
Bitcoin or some other cryptocurrency would be ideal for facilitating micro-transactions like this. Interestingly, the Hashcash concept was originally designed to fight spam, and later became one of the important ideas that made the invention of Bitcoin possible: http://en.wikipedia.org/wiki/Hashcash