Or by generating the hashes of all expected permutations of the password the user has just set, and keeping them until the next password is set to compare against. Granted, that would be a prodigious number, but technically doable.