Most of those fake registrations are probably coming from known spam IPs. Try something like this, your forum software may already support it...
http://www.stopforumspam.com/
I made a simple mod to the vbulletin PHP code for mine, disallowing a registration if the form was submitted within less than 5 seconds of it being loaded. Only bots can fill out a form that fast. That small change alone blocks about 20-30 attempts per day.