> Doesn't this mean that they are storing previous passwords in plaintext? Surely a massive no-no.
Not *necessarily*. For example: when you set your original password, they could also hash 1000 different forbidden variations of that password and store those 1000 hashes.
Bet you they don't though :-)
But more importantly, some common authentication systems *require* the plaintext password to be stored server-side anyway: Kerberos (and hence Active Directory) is the main example. It's fundamental to how it works.
Sure, it's an obvious point of attack, but every system has points of attack - as long as you know where those points of attack are you can take the appropriate precautions. And if your authentication server is compromised, you are toast anyway.