Digestión de mensaje (MD5) o Encriptación?

Está haciendo bien, los passwords de los usuarios se deben guardar no con cifrado de datos sino con una digestión, precisamente porque es irreversible y por lo tanto no es tan grave si alguien tiene acceso a esa tabla en la base de datos porque no pueden saber qué pasword tiene un usuario.

Para los usuarios que olvidan su password, lo que necesitas hacer es un mecanismo para que puedan resetearlo. Dependiendo del nivel de seguridad que quieras manejar será el mecanismo que utilices. Algunos que han cobrado cierta popularidad son:

• Liga temporal en mail: Consiste en crear un token temporal y ponerlo en un URL, marcar el usuario en un status que indica que olvidó su password, y mandarle un mail con ese URL. Cuando el usuario activa el URL con su navegador, tu server comprueba la validez del token, y le pide un nuevo password al usuario. La seguridad radica en que supuestamente sólo el usuario puede ver ese mail (y por lo tanto el URL) y el URL solamente funciona para cambiar el password una vez. El token puede ser un MD5 de email+password actual (que de por sí ya es un MD5) o alguna cosa similar; el token lo tienes que almacenar asociado al usuario para poderlo validar cuando recibas la petición de reiniciar password.
• Pregunta adicional a password: Cuando el usuario se registra le dejas elegir entre una serie de preguntas, o lo dejas hacer su propia pregunta y te pone su respuesta. Si olvida su password, le muestras la pregunta y te la tiene que responder correctamente. Este mecanismo no es tan efectivo porque el usuario puede haber también olvidado su respuesta, o bien puede haber puesto una pregunta que otras personas sepan responder y por lo tanto alguien puede secuestrar su cuenta fingiendo que olvidó su password. Puedes incrementar un poco la seguridad mandándole un URL temporal similar al del esquema anterior, pero cuando el usuario active la liga le muestras la pregunta (así no cualquiera puede ver la pregunta, tendrían que tener acceso a la cuenta de mail del usuario).

Dependiendo de la naturaleza de tu sistema y de sus usuarios, puede haber otros esquemas como autentificación directa o por un tercero, es decir que si yo olvido mi password puedo hablar por teléfono y si me piden mucha información que puedo corroborar, me dejan reiniciar mi password. O autentificación utilizando dos medios (hablo por teléfono y si convenzo al del call center de que soy yo, entonces ya me envian ese mail con la liga para reiniciar mi password, de modo que si alguien se hace pasar por mí telefónicamente, tendría que tener acceso a mi mail para poder resetear el password). O si hay algun tipo de jerarquía de usuarios, un usuario con un nivel más alto que yo puede reiniciar mi password, esto funciona si es alguien que yo conozco personalmente y le pido que lo haga.

En fin, tienes que pensar en la opción más adecuada para tu aplicación, pensando en que no sea una inconveniencia demasiado grande para los usuarios pero a la vez que no sea demasiado fácil para un impostor hacerse pasar por un usuario y poder reiniciar su password para secuestrar su cuenta.