When I've seen that "your password is too similar..." warning, it was with a system that required entering my current password to set a new password, so no need to store a previous version in plaintext.

Though another way around it is to apply a set of common transformations to your new password, hash it and see if it matches the previous one. I.e. if your current password is "Password123" and you try to set it to "Password1234", the system could truncate the last digit on the new password and see if it matches the current one.