I mean, you can do a paid relay without Web of Trust that solves the problem. My paid relay has had zero spam. It's the free relay that is plagued with the reply guy spam.
Discussion
Yeah, exactly as I said in my first comment. Multiple solutions approach (wot + paid relays + pow) and you can get rid of spammers in >90% rate. Not perfect solutions, better ones eventually can be developed, but this is what we have for today