EL método MD5 ya no es tan recomendado como antes. Te sugiero que intentes con métodos como SHA1 o PHPASS
http://www.openwall.com/phpass/
Lo que es importante, más que el mecanismo de hashing que utilices, es reforzar en tu aplicación el uso de contraseñas más difíciles de crackear ( porque los ataques por bruteforcing siguen existiendo). Es un dolor de huevos para el usuario, pero en definitiva es encontrar un balance entre seguridad y utilidad.
Saludos !