I believe this situation would be similar to many others out there, so maybe some of you can shed some light...

Supposedly, when making password changes through MS exchange every 90 days, you cannot use any simple variation of one of your old passwords, up to whatever limit the admin's set for a system.

My question: If your previous passwords are only stored as hashes, how can they check for the "just changed one letter" case. Wouldn't they have to have access to the old plain-text passwords in order to make those comparisons?

The only other thing I can think of is if upon original creation of a password, they also stored all other one character permutations of it, so that they can be banned later?