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
I sign up for a mailing list.
The mailing list mail server contacts my mail server.
My mail server presents to me a request for free delivery.
I approve it.
My mail server gives the mailing list server a secret token.
Each mailing list message includes proof that the message has been blessed by the sender and that the sending server knows the token.
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.
Dunno, I feel like we should just charge for mailing lists too. Or use usenet!
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'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.