Have you ever dealt with people whose interest was not just to spam but to vandalize? I've decided, maybe the best thing is to just put in place a really annoying CAPTCHA like Asirra that everyone has to deal with for every edit, till I manually put them in the Editor group. I used to only require the CAPTCHA for edits that add external links, but the vandals don't care about that; they're fine with just deleting or adding a bunch of text. Plus of course it's important to deprive all but trusted users of the reupload right, I found out the hard way. I'm working on blocking the open proxies too, although I have mixed feelings about that because I think some good users, especially of controversial wikis whose content borders on illegal, use proxies to avoid government surveillance.
I might create some sort of automated mass revert tool; I started work on it but it's hard to stay motivated. If you have other ideas, you can put them at countervandalism development. Thanks.