Quote from BeeJesus
Use a free dynamic DNS service. NoIP has one that's really easy to use, but if you want to take care of the problem completely you can always just install DD-WRT on your router and have it update your dynamic DNS with it's current public IP.
Good suggestions, but not sure this will 100% fix it.
My best advice would be to setup a no-ip redirect as mentioned above, but more important would be to make sure your server is online as much as possible. The more often the machine is connectable when a dns update hits the more likely it is for the dns cache to be aware there is a server at that IP.