Difference between reverse lookup tables and rainbow tables

In this case you could, upon registration, generate a hash of the entered password for every salt used so far, then check these salted and hashed passwords against all the passwords already stored.

You could even cache all the salts used so far, this is potentially a smaller list than having to loop through all passwords every time to collect these.

If that is too expensive to compute on each registration, limit the number of salts you generate (pick randomly from a limited list) to reduce calculation time. That'll still be safer (by far) than storing plain text passwords.

Note that if this is just for the sake of fraud detection, a security breach and resulting (huge) negative publicity is going to cost you much more, wiping out any advantages you gained from catching a few fraudsters this way.

Store the hashes and verify an entered password against those stored hashes, the same way you verify a password when logging in. You would have to generate 'alternative' passwords from the one given based on numerical patterns to detect your 'minimal' changes.

On login, you verify the entered password against a hash already, there is no need to store the password in plaintext. The same trick works when it comes to changing a password, simply check the entered and 'minimal change' generated passwords against the historical hashes. If the new password is satisfactory, move the current password hash over to the historical set, and replace it with a new hash for the new password.