Require a special character, but reject whatever one they use

[jmorahan]

"Password must contain a special character"
but if they add say a % then
"Password must not contain the following character: %"

This would of course make the fallback message unreachable. If that's not desired, leave some exceptions - enough to allow just one emoticon, for example.

[MichaelNMaggs]

Nice idea. Probably worth allowing a couple of reasonably common characters such as "&" and "^" to make it possible for them to get to the next level without giving up