MD5 no lo recomienda ni php.net , usa crypt , por que sucede que te genera distintas contraseñas por que el salt se esta generando aleatoriamente debes especificar el salt y el algoritmo siempre seran iguales para que las contraseñas generen el mismo resultado
yo te recomiendo minimo 8 caracteres y alguna mayuscula, alguna minuscula y algun numero eso sea obligatorio.
http://www.forosdelweb.com/f18/segur...ml#post4421471