A system I use not only has that requirement (along with a very insane set of requirements like "no patterns like 123 or ABC"), but they also NEVER let you reuse a password.
Which means they have a database of every password I've ever used on a machine somewhere, hashed or otherwise.
So the annoying workaround is to append year+month on the end of each password (which I was basically told to do when first setting up my account). So combined with a "maximum 10 characters" leaves 6 for my actual password...