Another idea for a potential technical solution, this one provided by the user Mirimir on the Tor mailing list. I thought this was actually a pretty good idea.
Wikimedia could authenticate users with GnuPG keys. As part of the process of creating a new account, Wikimedia could randomly specify the key ID (or even a longer piece of the fingerprint) of the key that the user needs to generate. Generating the key would require arbitrarily great effort, but would impose negligible cost on Wikimedia or users during subsequent use. Although there's nothing special about such GnuPG keys as proof of work, they're more generally useful.
As a proof of work I think it works out pretty well. The cost of creating a key with a given fingerprint is non-trivial, but low enough that someone wishing to create an account to edit might well go through with it if they knew it would only be a one-time thing.
This doesn't completely eliminate the issue of socks, but honestly if we make the key generation time reasonably long, it would probably deter most socks as they might as well just drive to the nearest Starbucks.
Someone else on the Tor mailing list suggested that we basically relax IPBE, which while not on topic for this list, I thought I'd mention just because it has been mentioned. They actually basically described our current system, except with the getting the IPBE stage a lot easier.
The following was also pointed out to me:
[I]t's also trivial to evade using proxies, with or without Tor. Blocking Tor (or even all known proxies) only stops the clueless. Anyone serious about evading a block could just use a private proxy on AWS (via Tor). [snip] The bottom line is that blocking Tor harms numerous innocent users, and by no means excludes seriously malicious users.
I did respond to this to explain our concerns, which is what netted the GPG idea. Does anyone see any glaringly obvious problems with requiring an easily blockable and difficult to create proof of work to edit via Tor?
Thank you, Derric Atzrott