Aggiungo che md5 è un algoritmo ormai insicuro: opterei per qualcosa che sia ALMENO sha1...

Per quanto riguarda il fatto di generare un hash diverso da memorizzare nel database, a quel punto, ti conviene fare tutto da db e lasciar perdere i cookie. Personalmente, non ho mai trovato i cookie sicuri... se usi algoritmi robusti e una password tosta, è sufficiente. Tanto, se ti devono bucare, ti bucano lo stesso
Scherzi a parte, io farei tutto da db.