One of the most annoying things about maintaining good password procedures is the fact that various places have different requirements. Some sites I use require one capital letter and one special character (100%Beef!), whereas others forbid special characters but require numbers. Many places have minimum password lengths, while a few especially annoying ones have relatively short maximum password lengths. Relatively few permit you to use a passphrase.
The best option would be to permit an unlimited string, including whatever punctuation and special characters are desired. Using a string basically foils brute force attacks, as the result of the sheer number of combinations. A hardcore password like “Sz5XULBKwPtI” is probably no more secure (and certainly much less memorable) than a custom phrase like: “The thing I most enjoyed about Paris, France was having picnics in the evenings.” Even if you only permit letters and numbers, each additional character increases the maximum possible length of a brute force search by a factor of 36: 62 if the passphrase is case sensitive.
Attacks not based on brute force (such as those where keystrokes are logged or passwords are otherwise intercepted) can naturally be carried out regardless of the strength of the password itself. What a passphrase system would allow is a high degree of security along with lessened requirements for obscure memorization. All it would take is a few minor code changes here and there, after all.