If you were to remake email from the ground up, how would you solve the spam problem while keeping it as decentralized of a system as it is now?
There are some interesting (I'm not sure "compelling" or "strong" is necessarily the case) arguments to be made for enabling open relays and other forms of unauthenticated messaging. John Gilmore of EFF has fought that battle for a long time, and still runs an open relay on toad.com.
Signing and authentication measures (particularly on header data) have to be both standard and quick to process.
Methods which increase the costs of delivery -- pacing receipt rates from a given IP or block, can help. Being able to specify receipt priorities: high for IPs and ranges with which frequent legitimate business is transacted, very slow for most others, would also be useful. Along with a lot of built-in support for this.
Killing :80 and moving to entirely secured ports wouldn't be a bad move either.
By "secure port", I mean forcing encryption of all over-the-wire traffic. It's happening now in many cases with STARTTLS (modulo utter brokenness of the CA and SSL/TLS systems), but that's still only opportunistic.
And of course, encrypting payloads would be vastly preferable. Headers as well other than absolutely required for delivery.
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.
Splitting these up converts one impossible problem into a tricky but mostly solved problem (delivery) and a hard problem that has to be addressed anyway (internet identity)