Certs against Spam
I previously suggested an anti-censorship multiplier of around 1/5. This is way too high - a multiplier of 1/100 or even 1/1000 would be able to make spam not worth doing, since spammers rely on being able to reach millions of users. Not eliminating peers which were eliminated by less than 100 or 1000 anti-certs could also help reduce false positives.
The extreme looseness of these values indicates that stopping spam with certs, once the necessary infrastructure is in place and the right approach is taken, is actually very easy.
Tickets against Spam
Penny Black has an ticketing system. There are a few obvious improvements to this sytem though, which I'll explain now.
Rather than sending back simple tickets, the server should send back pairs of one time passwords and their identifiers. When sending mail, rather than including the one time password, the mailer includes the identifier and a MAC of the hash of the message based on the one time password. When the recipient gets the mail, they query the token server with the id, hash, and MAC, and the token server responds with whether it's valid or not.
With this approach, there is no need to worry about a spammer intercepting a whole bunch of other peoples's mail and using their tickets. There's also no pop-style problems with dropped connections losing mail, since the ticket server can remember which hash was used with which ticket and respond idempotently that it's still valid later on.
The proper encoding of tickets is in a header line, and the hash should be of the Subject, From, and To lines, and the message body. This way it's possible for more than one kind of ticket to be put in the headers, if more become widespread in the future.
I think this technique could go a long way to stopping spam, and make Microsoft quite a bit of money in the process. They're one of the few companies positioned to be able to make such a system ubiquitous. I think $100 for 10,000 tickets is the wrong price point though. I'd be willing to pay $10 for 1000 tickets, if that really made sure my mail would get through any spam filter.