Systems like that probably do have some form of plain text password history which is very wrong. They might also do some basic common transforms of the password (Increment the numbers, did the hash match? Decrement the numbers, did the password match? Swap case around, did the password match?) but I do agree that's probably a pretty big stretch versus taking the easier (and worse) way to make that anti-feature.

I'm not saying that everyone does it right, I'm just saying having a password history enforcement does not require them to keep plaintext passwords. You don't need to "keep everyone’s password and previous password around in a database" in order to have some form of password history enforcement.