If they're using pbkdf2, scrypt, bcrypt, etc., there's a much better option than attempting to brute force a database of salted passwords.

You could check a lot (depending on language speed) of common passwords whenever a password is chosen, or during login, when you still have the password in cleartext. When it passes the checks, set a flag for that user so that the check doesn't have to be repeated.

If it takes to long to do during login, have a counter that keeps track of where in a list of passwords the checker is at, and do N more each login.

According to [1], the 100 most frequently used passwords are used by 40% of people, and the 500 most frequently used passwords are used by 71% of people. So you can increase security for over half of your users simply by disallowing the 200 most commonly used passwords. This set of passwords is small enough to fit in an in-memory list, so you don't even need to use a database for that.

I don't think there's much need to check for common passwords at each login, provided that none of your users are allowed to use such passwords in the first place. You might get more security by banning IPs that try more than a few of those common passwords in a short time (it's a useful way to detect brute-force attempts), but in fact you should be banning any IP that generates more than a few failed logins in a short time.

[1] http://xato.net/passwords/more-top-worst-passwords/

Another measure I use on my webapps is calculating how many bits of entropy a password contains, and ban anything less than ~40 bits (the threshold depends on the target demographic). An 8-digit number has 10^8 = 26.5 bits of entropy. An 8-char lowercase string has 26^8 = 37.6 bits of entropy (unless it's a common word). A mixed-case 8-char string that also contains numbers has (26+26+10)^8 = 47.6 bits of entropy. This method has the advantage that I don't need to specify annoying rules like "one lowercase, one uppercase, one symbol, etc." Simpler passwords can be allowed if they are long enough, and complex passwords can be banned if they are too short.

The "unless it's a common word" thing is the problem, really. I tried to do a more Markovian filter at my work and it bombed -- nobody enjoyed trying to get around its entropy restrictions. All it did was assume that your next letter would be predictably "like" your last one, so "password1" would have just one domain change in it. I didn't even go through, e.g., John the Ripper's dictionary to build an optimized order for going through letters.

Ban common words. Ban common words with 1-2 numbers attached to the end. Ban common words with 1-2 letters replaced with similar-looking numbers. But unless your website deals with very sensitive information, I don't think it's an efficient use of resources to try to use a more sophisticated filter. Simply imposing a logarithmic delay between login attempts, and banning IPs / disabling accounts after a certain number of failed attempts, go a long way toward protecting any password that isn't in the top 1000.

"password1" is too easy to brute-force. "pAssword072" is not even in the top 10000, and therefore it is already stronger than at least 98.8% of passwords that are out there.

The idea is to allow weaker passwords for the sake of convenience, but compensate for their weakness by adding protections in other areas. For example, you might require users with weaker passwords to change their passwords more often, disable their accounts more aggressively when a brute-force attack is suspected, or use more rounds of bcrypt to encrypt their passwords. Some of these measures will be helpful even in the case of a database breach.