Have you considered scripting it? For a while I worked at a place that required changing passwords every 60 days and it couldn't have been one of your previous 24 passwords. When checking out the policy I noticed there was no minimum password age so a quick for loop later and Bob becomes your mother's brother. Quickly cycling through 24 random passwords and back to my secure one and no more just adding the month/year.

Of course I reported it to cyber and about a year later they added a minimum age, now I'm hoping to get them to address an issue in AD that sidesteps changing passwords (though that one may be around for a while).