I tried just about every idea ever mentioned and none really seemed to work. I even went as far as to purchase a copy of xrummer to see how this was being done. (believe me.. it's one seriously powerful program that wp can't even hope to keep up with unfortunately).
In the end the one thing that ended up working for me was registration through obscurity.
Let me explain what I mean by that.
I have a site that uses multiple different pieces of software, wordpress, vbulletin, photopost, and a few others. Every single one of those software pieces all have the same problem with spam registrations.
It wasn't until I actually bridged all the scripts together with my own custom home-made registration/login system that my spam problem went away. I even made sure to leave in the meta values saying the engine is wp,vb,photopost,etc.. that way all the bots believe I am using that software, which I am.
The only problem for the bots is that my registration page links are completely custom. This means that the 'bot' comes to my site, sees wordpress in the header and then uses its 'wordpress' logic to attack the site. The problem is my registration is different so the bot's engine does not work.
Now xrummer could always program in a new set of algorithms that would break right into my site should they want to. The only saving grace is my sites all use different custom registration systems, and they are not large like facebook. Mean's I am a target so small that they don't even bother with me.
The only system I have ever come across that works nearly 100% of the time is one using voiceprint authorization. I won't mention the site, but basically the first time I went there I had to enter my phone number. A few minutes later I received a call from a bot that had me repeat a sentence. That got me into the system.
When I was 'promoted' as an owner of the software I received a call again and had to repeat the sentence again. It took 2 attempts because the software was making sure the voice matched.
Another option is to require sms verification. There are a number of companies providing this service for a fee.
hope these ideas help to provide some inspiration