Not only are the bots registering but surprisingly they created around 500 subsites on my site. 

For example if my site is http://www.mywebsite.com/

They created http://www.mywebsite.com/xyz1 , http://www.mywebsite.com/xyz2 etc

I just wasted more than 1 hour on deleting all these subsites and I wonder how did the bots manage to create them? 

The bots have been registering like anything in the last one week and on top of this now this new problem has crept up.

Could the updation of any plugin have triggered this ? Or could it be that these are some new ingenious bots that have found ways to bypass recaptcha. But had this been the case, then by now all the sites using recaptcha would have been affected.

If I say I'm frustrated-that would really be an understatement. I seriously don't know what to do! Sorry for the rant...

I think you need to be discussing this with your host to find out how the site has been compromised. It is, after all, also in their interest to help and take it seriously.

Worth checking if your WordPress is up to date as well. Always remember that often a version with a third digit of more than zero has often been put out due to a security issue and that security issue will be known by people wanting to take advantage of it.

Thanks Andy. Will do both and update you. I really need to make headway into this before they wreck any more havoc.

Please let us know what they say...

Quick update. The solution that finally worked is that I regenerated the recaptcha keys for my website. Spam registrations have almost stopped. I'm not sure though regenerating the recaptcha keys actually did this(but whatever did it, I'm happy)  What do you think guys could regenerating keys could have any effect ?

Speaking purely for myself I have not used recapthcha so can't really comment but it doesn't sound like a bad thing to do and if it helps then hey - just do it is what I say!

Haha. True

I had been running Bad Behavior Plugin but found it blocks lots of blog / forum posts from the Google bot among other legitimate crawlers. Tweeting posts sends a hoard of bots hiding behind Amazon's Cesspool. Hard to block when the source is hidden, might be blocking a good crawler.

I am running a 60+ percent of bots vs humans. It's still a problem and a huge waist of server resources. No real solution in sight that i have found.

Wordfence is fantastic.  Especially the paid version.  It handles pretty much everything, without any effort on your part. It also allows you to easily block entire countries... pretty much anything and everything you might want or need.

I installed it after my site was so badly hacked it took us a month to clean it up. I also lost four months of content.  I've had no trouble, since. It's a lot better to lock the door(s) than to try to get rid of trouble once you've been breached! 

WordFence does work well but blocks after the bad guys hit your server sucking up precious resources. CloudFlare on the other hand does pretty much the same thing but stops threats before they reach your server. CF allows blocking / challenging countries and blocking whole AS and IP ranges. Much better solution and is free!