Passwords don't work. Any password has a finite chance of being guessed. A good password is just less likely to be guessed then a simple password. A password is hard to guess if it is randomly chosen from a large pool of passwords. However, this concept isn't always understood well. Requiring (instead of just allowing) a password to include special characters and numbers does not actually extend the space of possible password, it may actually reduce it as some passwords are no longer "legal". Aside from that, the number of distinct passwords that people actually chose may not increase.
Let's say we require 10 characters, one has to be a number and one has to be a special character. The remainder may be any characters (special, number or upper/lower case letter). There are 10 numbers, 26 letters and typically another 32 printable special characters that are easily reached on a US keyboard. If we allow any combination of these, and exactly 10 characters long, we do obtain 96^10 difference possible passwords. If we require that at least one has to be a number, and one has to be a special characters, we only allow for 10*32*96^8 different passwords. A minor difference in password strength. But the more restrictive your password policy, the smaller the space of allowed passwords.
The next part is more psychological and hard to express in a simple equation. The fact is that there are only so many passwords that people are able to memorize. As a result, some passwords are used much more frequently then others, even if specific guidelines are provided (like requirements to include numbers/special characters). As an example, if users normally prefer the password '12345', they may just add a '!' if a special character is required. The new most popular password may be '12345!'.
Researchers from Microsoft and Harvard recently published a much discussed paper covering this aspect of passwords . As a result, the paper suggests to prevent users from picking popular passwords, rather then picking "difficult" passwords. The difference is subtle but important: If we only require a special character, "password!" would be considered a strong password. The proposed system would consider any password weak if it is selected by multiple users.
In the end, what really matters is not if a password is long and contains many characters, but if a password is likely to be included in an attackers list of passwords to try. Many times, attackers will only use a very small (3-10) list of passwords, hoping that one of your users picked one of the weak passwords. The real goal of a good password is to be not included in common password lists.
What we need is a database that will tell us which passwords are most common. However, we should not store passwords in the clear, not even if they are not associated with specific accounts. As a result, we need to come up with a "hash" that will represent these passwords sufficiently. This hash should be different from the hash used to store the password. First of all, we mind collisions less. For the actual account data, collisions are a problem as multiple passwords could be used to access the account. For the list of most popular passwords, collisions would lead to false positives, in which case a less popular password would be considered popular. Not a big deal as long as it reasonable. In a limited fashion, these collisions help improve security as an attacker will not be able to enumerate the actual most popular password. The authors of the above paper propose the use of a "count-min sketch" which is very efficient to look up the frequency of values. The passwords itself are not stored in the clear, only the derivative of hash functions and the passwords are not linked to the accounts other then in the (salted and hashed) account table.
What's really missing is a strong successor of passwords. There are many options, like various two factor authentication schemes, but none of them is as easily and cheaply implemented as passwords.