Well, if you had like 4 million IPs listed as blocked in apache config files, It would probably degrade performance solely due to the time it takes to read/cache all of those.
Now, I'm no Apache expert, and don't claim to be....
Is it possible to deny blocks of IP addresses (like a real firewall)?
For example, blocking 10.0.0.0/24 instead of 10.0.0.1, 10.0.0.2, 10.0.0.3, etc... ?
That way, you could just block a "troublesome" group of IP addresses all at once.
Another option, but yet again, I'm hypothesizing, haven't actually looked into it:
could you use some authentication module tied in with a database (mod_auth_mysql?), so the database does the grunt work of the lookup?
Just an idea, I have no idea if it's possible. 🙂