Sure, but if you run through a few thousand hashes to check for similarity, an attacker can check for the couple thousand most popular passwords in the same amo

Sure, but if you run through a few thousand hashes to check for similarity, an attacker can check for the couple thousand most popular passwords in the same amount of time. It is possible to throw enough money at it to make an attack uneconomical, but that's expensive. (Also, DoS. Note that you can't stop people from changing passwords when the system is under load, as that sets you up for a combined compromise-password-hashes-then-DoS attack...)