I would expect that you'd just compare the hash, effectively performing half of the log in process to check if the password's okay. I imagine it'd be pretty costly in terms of performance if every time you wanted to create a new user you had to hash the password, then check against a (potentially huge) table to see if that password had been used >X times.

Hopefully I'm being short-sighted or missing something that'd mean this could be done simply and quickly, because in theory it sounds like quite a good idea.