i believe you should simply do like windows AD does, and store the hash of the password, and not the password itself.
then you compare the potential new password to the hash;
maybe save the last ten passwords as a delimited string of hash values, which you cna split with dbo.DelimitedSplit8k, and compare all in that virtual table.
edit: Sean already suggested the same, of saving salted hashes of the password.
Lowell