The type malicious bots you describe can connect through open proxies all over the world (typically without permission), each having different IP addresses. They can also use trojans and viruses on hijacked client computers/servers to do their work. In other words, Drupal's built-in flood control system, that uses IP-addresses for blocking, is no good for dealing with this type of attack. If the flood system causes problems for you ("locks everyone out"), you need to reconfigure it or turn it off.
You can do this by adding one or both of the following pair of configuration settings to your site's
// Set per-IP failed login attempt limit to max and window to 5 seconds
$conf['user_failed_login_ip_limit'] = PHP_INT_MAX;
$conf['user_failed_login_ip_window'] = 5;
// Set per-user failed login attempt limit to max and window to 5 seconds
$conf['user_failed_login_user_limit'] = PHP_INT_MAX;
$conf['user_failed_login_user_window'] = 5;
In that way, no-one will be locked out.
Instead of using the built-in flood control in Drupal, try using Apache ModSecurity to limit bots access to your server, filtering on content (POST requests), instead of IP-address.
From its documentation on HTTP Traffic Logging:
Web servers are typically well-equipped to log traffic in a form
useful for marketing analyses, but fall short logging traffic to web
applications. In particular, most are not capable of logging the
request bodies. Your adversaries know this, and that is why most
attacks are now carried out via POST requests, rendering your systems
blind. ModSecurity makes full HTTP transaction logging possible,
allowing complete requests and responses to be logged. Its logging
facilities also allow fine-grained decisions to be made about exactly
what is logged and when, ensuring only the relevant data is recorded.
First discover the pattern in the POST requests the bots make, and use Apache to block them.