When I moved to a new apartment a few months ago, I started keeping track of all the banks, bills, etc. I had to change my address with. I recently migrated these into RTM, along with a URL of where I can change it online. The due date is the first of the month our lease expires.
I'm not sure if we'll be moving when it expires, but if we do, I'll have all the addresses I need to change at that point. Otherwise I can just postpone all of the due dates by a year.

Whenever I find myself giving someone my address, I'll add it to this list.