New User Flood
Now that I had some time to think on the problem. I do remember using one really simple and really effective tool to prevent bots from registering.
It's called a reverse captcha. Basically you use in combination with normal captcha, but you are suppose to leave it blank. Give it a id and name like "captcha" and bots will almost always fill it in with something. You then either hide it via css (most bots don't read css, and even if they do, it often falls into the machine vision problem), or write next to it that you are not suppose to fill it in.
Also prevent registration from non-local referrers should also reduce the amount of bot registrations.
There is also the twobox captcha. Where you have one set of instructions for two text boxes, that have a value already set. You tell the user to change the value of one, but not the other (usually something simple). This requires usually a custom bot to attack the site, since such a captcha is beyond the normal (which generally only attack standard captcha implementations, such as recaptcha).
