They could in theory hash the new password with every salt on every other account and see if there is a match... but that seems unrealistic, and if they can do

They could in theory hash the new password with every salt on every other account and see if there is a match... but that seems unrealistic, and if they can do it, it would imply that they are not using a slow hash algorithm such as bcrypt.