The big practical problem with certification-based reputation systems for preventing spam is that the attacker can selectively target any user on the planet to get a cert out of a confused person. A straightforward way of dealing with this is to simply select the people they must attack for them. In other words, rather than have someone collect certs, have someone who wants to join the system be assigned to several other people at random, they conduct a turing test by conversing with the applicant, and then if enough of them pass the person gets in.

This approach magically gets rid of all those complicated back propogation requirements, and has nice properties like you can start weighing the input of people who have previously been fooled by a bot. Notably, I've basically reinvented hotornot moderation, which goes to show what a well done site that is. This approach is also inherently very centralized, and basically winds up being a glorified captcha system.

Some disappointing practical advice can be derived from this: use captchas. When people tell me about their spam problems on the comments section of their weblog, I generally advise them to take Brad Templeton's approach. Force everyone commenting to answer the question 'What is my first name?' for their post to go through. Obviously other questions can be used, but that's a very good one so long as it doesn't become so common that spambots start to try to guess it automatedly. Technically trivial, but it works great.