I have one ISP where we have intermittent problems delivering messages to mailboxes hosted by that ISP. It is something related to DNS lookups, because when I clear the cache on our DNS server, the problem goes away. So, presumably it's changes on their end that cause the issue.
By default the Windows DNS server caches DNS lookups for 24 hours. However, I don't want to be manually clearing the cache on this each time the error occurs (or wait up to 24 hours to automatically resolve). The solution: modify the cache TTL.
In all of the forward lookup zones that you create, you can set the TTL for the zone or individual records. However, in the cache, you can't set the TTL by using the DNS Manager console. You can either use dnscmd.exe or edit the registry.
In HKLM\SYSTEM\CurrentControlSet\Services\DNS\Parameters, create a REG_DWORD value named MaxCacheTtl and provide a value in seconds. I did not find any documentation saying that this registry key works in Windows Server 2008, but tested it, and it does. There is documentation for Windows Server 2003 and earlier versions.
After setting the registry key, you need to restart the DNS server for the change to take effect.
UPDATE: A client started having this issues and I found a knowledgebase article that talks about this exact issue. Oddly the recommendation is to set the MaxCacheTtl at two days rather than shorter as I had done. See here: http://support.microsoft.com/kb/968372.
There is also a similar issue with 2008 R2 and 2008 R2 SP1 for which there is a hotfix. See here: http://support.microsoft.com/kb/2508835/en-us
UPDATE#2: We have now had several clients with this problem and the solution has always been to implement the MaxCacheTtl at two days. The hotfix has not ever resolved the issue for us.