[spinsser]

Why would they need to store the hash for all the combinations?

Why not generate a list of similar passwords to the new password, hash them all using the same salt of the previous password and then compare them.

[kbenson]

Depending on what is considered "similar", every extra password character may exponentially increase the number of similar passwords.

[joshvm]

Well in my case, there was only an 8 character limit, so there was a least a bound on it. I didn't investigate how far you could deviate from an old password before it was allowed though.