Not to mention that a 30-char purely alphabetic passphrase such as xkcd.com/936 is so much easier to remember (i.e. less likely to be written on a post-it note) and type into today's mobile devices (i.e. more likely to log out properly, because it's easier to log in the next time) than a 12-char password with two numbers and one symbol in it. What I'm trying to say is that there is more to password strength than the time it takes for a botnet to brute-force it. Humans are the weakest link in most security systems. If you want strong security, you need to design your system so that humans can interact with it without too much mental strain.
Nowadays, anything less than [\x20-\xFE]{8,64} is just a lame excuse for storing passwords in a plain-text VARCHAR field without proper escaping. Therefore, if your password policy as any more restrictive than [\x20-\xFE]{8,64}, I'm going to assume that you store my passwords in a plain-text VARCHAR field without proper escaping.