Have you tried rate limiting based on the user account? That should block a distributed attack since each login would count against the rate limit independent of the IP address.
How would that help in this situation? The attacker had a database of user/password pairs they were trying; they weren't trying to brute-force a particular account.
Oops, you're completely correct. I was thinking of the brute force scenario.