They don’t just store your current password. They keep the old hashes too. This error might really mean: “you’ve used this password before, you can’t use it again. We do this as people seam to think they can go back to already compromised passwords.”

Maybe time to look at a password manager.