Secondo me se uno perde la password e fa richiesta la vecchia va sempre eliminata, se uno non si ricorda la password per quello che ne sappiamo potrebbe aver scritto tutte le sue password su un foglietto e averlo perso.
Quindi genererei una nuova password di 8 cifre alfanumeriche casuali (come scritto da Sonounostrinato) e poi se all'utente non piace al primo login se la cambia.... semplice è semplice, anche se la password fosse difficile da ricordare (e dovrebbe esserlo se non la si è creata da soli) basta un copia incolla dalla mail la prima volta....
Questo poi è il sistema standard di forum e portali vari.

Se dovessi implementare un sistema più sicuro (non per un forum o un sito normale) imporrei che al primo login, dopo il recupero/generazione password provvisoria, venga cambiata per forza, in modo che quella sulla mail non sia più valida dopo usata.