No, you can do it safely. The idea is to have the password renewal process also ask for the previous password.
This means the password changing method doesn't need to store a plaintext password, but still has access to the old plaintext password when changing.
It's still not a great idea, but that's because nagging your users will see them choose worse passwords.
Actually it can be trivial as long as you can require the user to re-type the current password when entering a new password; check hash first, then check edit distance with the entered "current password" (and, of course, promptly throw it away once you know the edit distance.)
It does more than that, it keeps a hashed password history (which used to be in the user attr ntPasswdHistory, but is now "somewhere secret" afaik) according to the value of ms-DS-Password-History-Length attribute. OpenLDAP keeps these (ppolicy overlay) in the user object.
So, it can hash any proposed password and compare the history to make it's not been seen $recently (as an exact match, since it's comparing hashes).
It could also perform some minor permutations of any new password, and do the same history check to make sure you're not just changing the first or last character or digit. I don't know if it does this, but it could.
Not if the check is done client-side, so the plain password never leaves you local domain. Of course the check being done client-side means that it isn't difficult to skip if you are inclined to make a smidgin of effort.
Yes, what I meant to say that it doesn't even have to be done server-side, so the fact it happens doesn't imply the server ever sees the old password beyond it's initial setting.