Having everyone use a single central site for their messaging has tremendous benefits in terms of stopping spam. For one thing, there's no need to propogate data across the system. For another, it's reasonable to assume that the central site could make it sufficiently difficult to generate new ids that less than half the nodes in the system are spammers, which as we will see makes anti-spamming vastly easier.
My big problem with anti-certs up until now is that they enable censorship. I'm now convinced that censorship can be limited using the very simple mechanism of only allowing someone to anti-cert the sender of a message they actually received. It's probably a good idea to require that the anti-certing be done within a short period of time after the message is first read.
Now, for my improved algorithm for removing spammers. We would like for a spammer to be able to send out a fixed amount of spam for each node they compromise, and not get any benefit by making fake identities. Since we now have a concept of where the big island of nodes is, we can do exactly that. For a subset of nodes, we count the number of them who are certed by nodes in the big island. If that subset has 100 times as many spam marks as the externally certed nodes (or whatever the permitted amount of spam is) then none of the nodes in that subset are allowed to send out mail.
I'm not sure of a good algorithm for finding such subsets, but intuitively it doesn't seem like an intractable problem. Also, a reasonable case could be made for counting edges instead of nodes for the amount of spam allowed.
I'm quite happy with how workable this approach seems. It looks downright practical.