I still think that maybe:
1)Stop all registrations;
2)Look k at the database, look kinda when did the mass registration started (if any appened - I hope)
3)Unregister everybody from that point on. Not lock accounts - deregister them so that the true ones will be able to register under the same Login again;
4)Install a less bot friendly check;
5)Open registration again.