Lo que es mucho más crítico que una diversidad de símbolos no alfanuméricos es la longitud de la contraseña simple. Las máquinas especializadas de craqueo * existen desde hace años y son capaces de atacar con fuerza bruta todas las combinaciones de letras, números y símbolos, de hasta 10 caracteres (dado un atacante suficientemente motivado que está dispuesto a gastar miles de dólares en una computadora de craqueo de contraseñas, por supuesto.) En este entorno, es infructuoso discutir sobre un signo de exclamación en una contraseña de 8 caracteres. Exija que las contraseñas tengan al menos 12 o más caracteres, y tendrá una solución mucho más segura. Si te hace sentir más cómodo, también puedes requerir un dígito o un carácter en mayúscula. Otra mitigación es utilizar PBKDF2 para almacenar contraseñas, lo que hace que los crackers paralelos sean menos eficientes.
Ya hay muchas preguntas y respuestas en security.SE acerca de las políticas de contraseña recomendadas, deberías echar un vistazo a esas.
* Es una PC normal llena de tarjetas GPU y un programa CUDA masivamente paralelo para calcular hashes SHA-1; La última vez que lo miré podía calcular 348 mil millones de hashes SHA-1 por segundo. Dudo que el hardware se haya vuelto más lento con el tiempo.