Instead of freezing the account until it's unlocked by customer service, why not just lock it for increasingly longer periods of time? 2 seconds after the third failed attempt, 3 after the fourth, 5 after the sixth, 10 after the seventh, etc.
Not too inconvenient for legitimate users trying to remember their passwords, but it surely makes bruteforcing impossible (if by the 1,000th attempt they're having to wait an hour between attempts).