We've got a few customers at work, including ourselves, who use Windows Server 2008. But only one was experiencing this problem. A "good" (i.e. quick) workaround was simply clearing the DNS cache. However, it was obviously not a decent solution.

After more investigation it looked like it only affects servers using root hints, in some form. If a server was using recursive queries more, then the problem wouldn't reoccur as often. As it was only happening every few weeks we didn't look into it too much. But, after quite some time since we came across it and finally resorting to periodically casting an eye over technet's blogs it looks like setting the DNS Max TTL to 2 days or so stops the problem from occuring (nice...).