So why not have accounts temporarily lock after, say, 5 failed login tries, and e-mail the account holder that it appears someone is trying to hack their account?

The only thing the Captcha would defeat is if someone had a massive DB of login & password combos which are "legit" from some compromised site (and not just a brute force dictionary), and are using robots to try those combos at a bunch of common sites to find accounts where the person used the same username & password. I'm assuming that's what is being done, but it still seems like there would be better ways of doing this.

And you could still have humans try those stolen usernames & passwords on a few high-value sites (banks, hotels, airlines, etc.) to bypass the Captcha.