Interesting: a proposal (from Microsoft) to implement a "sender pays" scheme for email by a cycle tax, instead of an unworkable micropayment scheme:

De-spamming with a cycle tax - A summary and an extension idea

[Via Ole Eichhorn, via Dave Winer] Microsoft is noising around an anti-spam technique that would essentially create a cycle tax on each piece of e-mail. This is done by forcing a client computer that wants to submit e-mail to a server to solve a cryptographic problem of known difficulty set by the server, presumably by adding a challenge/response step in the mail protocol. To the normal sender of mail, the few second delay is no problem. For a spammer, it bogs down even networks of hijacked machines and reduces the flow of garbage into the network. There remains an interesting problem of the inter-server protocols, since replicating the same technique per message would become an egregious burden, but something must be done since hijacked relays are part of the problem. But there are a variety of options there: batching messages, trust networks among servers, throttled tiers of forwarding service based on the size of cycle tax provably paid by the originator.

This is one of the anti-spam options explored by a Microsoft Research project called Penny Black, named after the original postage stamp. It has the merit of creating a real cost, without requiring all the apparatus and problematic economics of a microtransaction infrastructure. Like Dave, I'll wait and see if it's a ploy by Microsoft to sink its proprietary hooks into the mail networks before I cheer too loud, but this does have potential.

[Due Diligence]

I haven't read all of the original article, but the basic scheme is probably workable. You just add an extra step in SMTP, just like authentication is handled today. Just like SMTP authentication is usually required before a server will relay messages for non-local IP addresses, you could require this before servers will accept messages from unknown servers. The mail server could base the complexity of the problem on a pile of things, like spam IP blacklists, previous traffic patterns, and so forth. So, if the server has some reason to believe that it's going to receive good mail from the peer, then it doesn't need to request authentication at all, while when dealing with random dialup IPs, it can request a fairly complex problem.

Now, this suffers from the usual implementation problems that all SMTP replacements (or mandatory enhancements, they're basically the same thing) suffer from--basically, it's worthless until most of the market is already using it, and that means that no one will probably ever deploy it. The basic idea seems sound, though. It'd probably make an interesting addition to new protocols, even if it's logistically hard to add to existing protocols.

My personal experience shows that Bayesian filters work really well for personal email. Paul Graham suggests that the recent anti-spam legislation plays right into our hands; while it doesn't do much to stop hard-core fraudulent spammers, it's going to destroy middle-of-the-road spammers, because decent filters will be 100% effective stopping their spam. Which means that we're winning, really. Some of his other ideas ("Filters that Fight Back," particularly) sound like they should be effective at raising the effective cost of spamming, and that's really everyone's goal: make spam uneconomical without destroying "regular" email. So, I'm not really sure that this cycle-tax plan really matters in the long run. But it's an interesting idea.