[tape_measure]

Would it be a bad idea to salt and hash probable increments of a password when it is changed? For example, password would be salted, hashed, and stored along with Password, password1, etc.

Then the system could reject these on the next password change without storage of the original plaintext password.

[tape_measure]

ixwt gave a better solution - do these calculations when the password is changed, not when it is set. Therefore, less storage is required