Protect site from flooding when user login is attacked by brute force

Question

I've been experiencing issues with bots trying to force their way into the website I manage. It seems to be a daily occurrence the the flood system is being triggered (I'm on D7).

I'm happy the the flood system is doing it's job and stopping the attacks, but the problem is the bots are using private IPs, so when the flood is triggered it just locks everyone out.

I would like to find out if there is a way to limit the amount of bots that are getting through to the actual login verification. I tried throwing hidden captcha on to the login form, which does an ok job of it, but even when it suspects a bot, it doesn't't stop the login verification, so the flood system still gets triggered. Does anyone know of anything I can put in front of that process to limit the amount of bots getting though? The less intrusive, obviously the better.