After three failed login attempts, send the user an email at his registered email address:

  John Doe:
  You have, or someone pretending to be you has attempted
  to log into xxx.com unsuccessfully 3 or more times.  
  To provide you with the utmost in security, xxx.com has
  put your account on a temporary hold.  You may remove
  this hold by logging in as follows.

  The next time you log in (and that time only), use your
  existing user name, plus the text, "+ZRYU3" (without
  the quotes), appended to your username.  Your password
  should be entered in the usual fashion.

  If the unsuccessful login was the result of forgetting
  your password, click THIS LINK to have your registered
  password hint emailed to you at this email address.

  We are sorry for the inconvenience.  If you have any
  questions or need further assistance you may email
  support at login-support@xxx.com.

  Sincerely,
  .....
[download]

I think the preceeding text pretty much explains the pholosophy. If three attempts fail, suspend until the user logs in with 'username+REY3Q', the suffix being a random set of ASCII characters known to be available on just about any keyboard; perhaps \w or \w\d.

Implementation wouldn't be terribly complex, and the only difficulty would be if users don't keep their email address up to date, or if they're too new to technology to understand the instructions.

If you're still concerned with a bot knowing about the suspension and trying to thwart it by guessing at the username alteration as well as the password, implement one of the $delay*=2; solutions for every guess at username. The delay still enables DOS attacks, but the attacker has to go an extra layer into the onion to accomplish the attack. And also, by adding an extra six unknown digits to the username, in addition to the already unknown password, you've made unauthorized access difficult enough that the attacker is likely to seek more fertile ground.

UPDATE: BrentDax suggested emailing a "...click on THIS LINK..." to the real user's email address. I think that's a fantastic modification to my original proposal, but believe that for those whos email clients don't support clickable links, and those whos email clients break links by mangling them in the process of wrapping text, it doesn't hurt to provide the "log in next time only username+random_stuff" as an alternate. There are people who simply can't click on a link in email and expect it to work right. The approach of enabling either option seems to be a good solution for those people.

Dave

"If I had my life to do over again, I'd be a plumber." -- Albert Einstein