It is stupidly simple to get around most sets of independently-evaluatable password complexity rules; minimum length, case requirements, non-alpha character requirements. "Password1", unless your name happens to be Joe Password, will get past most rule systems because it's at least 8 characters long, with a capital and a number. It's also the first thing any crackbot will try.
The cardinal rule of any password complexity requirement is, the harder you make your system to use, the fewer people will use it. This goes way beyond password complexity rules, but as the login screen (and the user registration screen you usually link to from there) are the first real interaction by the user with your system, the more unpleasant it is, the less your users will want to deal with it, and with you. This is especially important if you're trying to "sell" your system to users as a product they didn't know they needed, or if there are a lot of alternatives to you in the marketplace (like an online forum). Users in that situation will very quickly say "screw it, I'm out", and you are unlikely every to get them back.
A few additional rules naturally follow. One is that you inform the user clearly and simply of the rules you have in place, before they type in anything. It's not a security problem for the complexity rules you enforce to be public knowledge, unless those rules actually decrease possible entropy of acceptable passwords (which rules like a maximum length can do), and your user will be far less frustrated at your system than he would be if he had to learn the rules by reverse-engineering.
Another rule is, don't deviate too much from rules users expect. Most users are smart enough to understand that minimum complexity is for their own good, and they also know that the bars most sites and applications set are of similar height (6-8 character minimum, a capital letter and number, can't contain any of a few obvious words like "password"). Enforcing ridiculously long and complicated passwords in excess of the implied standard (minimum 20 characters, at least two groups of at least 4 numbers each and at least 5 symbols) is just going to piss people off, even if you tell them up front.
The last meta-rule I'll state is, don't enforce a rule for its own sake. Never use a rule just because you saw another site or application do it, or even just because it's best practice. There are reasons behind best practices, but you should know and understand those reasons, including why they may not apply in your situation, before Scotch-taping together a security policy.
The ruleset I usually like is:
- Minimum length of 8 characters.
- Either mixed case, number or symbols.
- Can't be composed only of a dictionary word.
- Can't contain any part of your name, username or birthdate (if I know these things)
- Can't have a "banned password" be 50% or more of the password. Banned passwords include any that have ever appeared on SplashData's Top 25 list, including most of the greats like "Password", "letmein", "12345678" etc, as well as any string that is "interesting" in IT security ("correcthorsebatterystaple", "orpheanbeholderscrydoubt") and any password previously used and known to have been compromised. The full list would be relatively short and easily displayed to users via a link from the list of rules.