Usually, when you change your password, you need to enter the old password first. This is useful for security, to ensure that someone walking by your computer can't very quickly change the password and lock you out while your back is turned. It also allows the server to enforce password distance rules. The server only needs to keep the old password in memory for as long as it takes to verify that the new password is sufficiently different from the old one. It never needs to store the unhashed password, and can erase the old hash as soon as it has stored the new one.
If the server checks equality with older passwords, not just the last one, that's a different story. It's easy enough to check password reuse with old hashes: for each old hash, compute the hash of the new password with the old salt and compare with the old hash value. On a properly configured system, this should take a few seconds.
It's a different matter if the server is checking similarity with older passwords, and not just equality with older passwords plus similarity with the previous one. If the server is using proper hashes, then it must try variations on the new password and hash each variation with all of the old salts. That could take minutes or more with a non-negligible number of variations. So if the server is complaining about similarity with an older password, I would be wary that they may be storing improperly-hashed passwords.
There is another approach for similarity, which is to store the hash of each password variation, each independently salted, as soon as the password is set. But that doesn't buy you much: the server still needs to calculate the hash of the new password with all these salts, which still takes a long time, too long for a typical password change.
A way to recover old passwords that actually works, but that I've never seen implemented anywhere, is to do the following on a password change, after prompting the user for the old password and before erasing the old password from memory:
- Derive a symmetric key from the new password (using a key strengthening algorithm).
- Derive a key from the old password in the same way.
- Decrypt the list of old passwords with the old key.
- Append the former password to the list.
- Make the policy checks — all prior passwords are known at this point. If the new password passes the checks…
- Encrypt the list of old passwords with the new key.
- Change the password and the encrypted list of prior passwords the database.
This is somewhat risky because if the current password is compromised, all prior passwords are also exposed. But it does allow to enforce a password distance policy to any number of prior passwords with a reasonable computation effort.