Transition
An obvious problem is how to transition from charging nothing for all your mail to charging something, without having everyone else do the same thing at the same time, or not getting any email ever again. There are a few ways we can ease this in.
The first and biggest problem is mailing lists. Coping with them at all is difficult: if you have a 5c mail going into the list, you somehow have to produce 5000 5c (or 30c) mails going out. Where’s the money come from? Obviously posters can’t afford it. An easy answer is the subscribers — if you subscribe for 500c, you can get 100 5c mails from the mailing list (and thus a full 500c refund!) before your subscription runs out. Coping with the initial subscription is easy too: you send a 5c subscription request, you get a 5c confirmation, and you reply to it.
All that’s well and good, but it doesn’t work unless the list manager is in on our scheme, which is the transition problem. If we’re going to solve it, we have to have an address in “our” control that accepts mails from the mailing list, without coins. It can either then verify them somehow (X-Mailing-List headers, eg) and add them to our inbox, or it can add a coin to them before forwarding them onto our real address. The latter lets you setup a subscription server during the transition that gateways old mailing lists into cashed up mailing lists for individual users. If the mailing list software doesn’t give out lists of subscribers, you can use an address like aj-123456789abcdef@example.com that’s unpredictable and different for each list to avoid spammers and strangers getting you directly. If it does give out lists of subscribers, you need to manage to drop non-list posts to that address somehow, which could get a bit flakey, but should be reliable enough. The other problem is posting to the list — if the list accepts posts from anyone (and is thus a spam trap itself), then you don’t have a problem; but if it’s for subscribers only, you do. You probably have to subscribe twice, and either elect for your real address not to receive mail, or just drop the mails that go there. All of that should be doable.
The next problem is that of strangers emailing you. This is the set of people to whom spammers belong, but it also contains “friends you haven’t met yet”. Obviously the most convenient thing for them to do is to setup ecash themselves, so that needs to be easy. Basically, you pretty much have to bounce them a reply saying “You haven’t paid enough money” and get them to either resend it with a coin, or to go to some website and confirm it. Ideally you want going to the website to be about as easy as it would be if they installed all the software locally. Basically, that website has to store the rejected mails, and allow you to send them on. The URL can contain the Message-ID easily enough, and maybe a nonce. Ways of approving mails could include presenting a coin (if your email software can’t cope), or doing one of the cute problems that aren’t difficult, but require human interaction. You could do this in the same way as subscriptions (ie, put up 500c, for every 100 emails from strangers, and recycle the funds), or you could let people get new coins from the mint when they solve such problems.
Those are really the easy problems, though. The hard one is dealing with friends emailing you. You can’t just tell them to get a new email program, and you can’t expect them to bother solving irritating problems whenever they want to mail you. You also can’t just drop their email. The only way to solve this problem is to hope they change their minds eventually. Work arounds have to involve identifying mails from friends and restricting them less. Possible ways to do so are by special addresses (aj-foo-123456) which suck, matching on From: lines, which spammers can and do fake, or cryptographic signatures, which no one does. Some combination of those would probably work; which means you definitely want your filter to cope well with all of them.
The final issue here is getting coins into the system. One way is letting people buy coins for real money. That seems unlikely to happen, at least early on. Another is for them to do computationally intensive stuff like run a distributed.net client, which seems like a good idea, although working out how many coins for how many blocks might be difficlt. Proving you’re a human is also probably worth a handful of coins. Basically, you need to have enough coins to cope with a few days’ mailing list mails, and enough to attach to all the mails you want to send. That might be, say, 5000c for the lists, and 20c a day for mails, which shouldn’t be too hard to manage. If you equate $1 with 1000c, it’s not particularly expensive to set up, and $0.005 per spam, would net me $350/yr, which ought to be horrendously unaffordable for spammers.