The whole idea behind the approach I published was to lower the amount of user requests for password changes. In my case, it worked like a charm.
Doctor Grauman's idea is very interesting. Unfortunately, I doubt many of my end users know their history quite that well.
Another approach, and this is what I do for my domain administrator accounts, is to use a mathematical equation. Something like the equation of a line:
Y=2.5x+50
That password has all the things you need. Capital and small letters, numbers, and symbols. And, come password change time, increment one or both of the numbers.
Also, in the case of both approaches I mentioned, you don't have to increment your number by 1. You could go by 10's or 25's if that will make the last number you used easier to remember.
JamesNT