Pas besoin d'avoir un historique, pour le premier point ; une table de hash des anciens mots de passe suffit (mais pas de sel, en effet). C'est, il me semble, ce qu'utilise Windows.
Pour les 75% de différence, là, c'est effectivement un vrai problème. Au lieu de ça, il vaudrait mieux mettre un contrôle tout con (pas forcément utile, mais vendeur) : le mot de passe ne peut pas contenir tout, partie substantielle ou dérivation de l'identifiant, du nom et/ou du prénom (du pseudo) de la personne.