You don't need to keep someone's plaintext password in the database to compare. Just re-calculate hashes against historical hashes at new password time. If the hashing process is secure keeping a few old hashes isn't really a security concern, especially if people are actually using unique passwords.
Now, normally this is tied to an automatic password rotation policy, because allowing a previous password completely undermines a rotation policy. The real thing to complain about and attack are these rotation policies, which are probably more harmful than helpful.
You should never keep plain text passwords. bcrypt it at the very least. I'm referring to keeping a history of those hashes around to compare against other leaked databases one would find on the dark web. Having a history of the last password hashes are n+1 as bad as storing a password hash.
I have seen sites that complain if your password is too similar to a previous password, and that shouldn't be possible with hashes. So who knows of the sites that look for exact matches are looking at the hashes or not.
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.
correct. security often compromises itself for sake of itself. It's stupid and is the "lowest denominator" thinking. If they store a history of hashes, one could compare them but not classify similarity. Only whether it was used previously or not. I get down voted by the security folks who think this practice is a good idea. It's not. It's a horrible idea. So is enforcing 30m session/cookie timeouts. Or constantly scanning your machine for "threats". Pegging your CPU at 100%, 100% of the time. Security folks are like the mall cops of IT. Not saying that's everybody. There's some terminators out there, or Jack Ryans, but most are Paul Blart. They want to read your emails, see your browsing history, read your chats, get offended if you criticize them, bring you into HR if you circumvent their crappy jump box backdoor into AWS...
Now, normally this is tied to an automatic password rotation policy, because allowing a previous password completely undermines a rotation policy. The real thing to complain about and attack are these rotation policies, which are probably more harmful than helpful.