Use exponential backoff for that user. If the user gets the password wrong X times, wait for N minutes. If the user gets the password wrong X + Y times, wait for N + M minutes, and so on. If the user gets it wrong too many times, require manual unlocking via customer service. 'Course, this annoys people, so use with care.
You might want to extend it to blocking by IP too if some IP is trying a lot of different user combinations. Problem with that is basically that you might be under a DDoS attack and they're not easy to protect against.