If you spend the time building a system to search those half billion passwords when you’re users are signing up, you should focus on building a login rate limiting system so it’s not possible to brute force someone’s password.
If you hit two valid accounts [1] with bad passwords in a few ACCEPTABLE_UNIT_OF_TIME, it’s captcha time.
Thresholding isn’t just action per IP it’s being smart about how people are going to attack your system. It requires thought and upkeep.
[0] Previous thoughts on bot detection: https://news.ycombinator.com/item?id=16182405
[1] Also, if your login identifier and your public “display names” (usernames) are the same thing, that is a disservice to your users’ security.
Maybe salt your passwords, use some stretches, and a decent algorithm instead of MD5, SHA1, etc.
Also stay up on algorithms and roll your users over to new ones over time.
Either you have some EXTREME legacy or lazy engineers. Doing it right doesn’t take long.