You refuse to allow login during the delay period. That is, after the 5th failed login, for the next 16 seconds, if the user tries to login, you say "Wait sometime before trying again." You do not accept and check the credentials supplied during this time. You simply refuse to begin the authentication process until the delay period has elapsed.
And exponential backoff is fine but not when it gets to be too much, it turns into a DoS problem. You could try to key it by IP and never let it go past, say, 2 minutes per source IP.
i.e., if me simply knowing someone's account name lets me disable their account for the next day or longer, that's a big problem.
It's not just tying up threads you want to avoid but any unreasonable resource consumption you can. You maybe for example want to make sure the delay timeout you store for that account (by comparing current time to a "notBefore" timestamp or what not) is not going to cause a DB lookup each time, etc.
