I had trouble with that when I was using a Windows 2003 server with RRAS for NAT duties... It was a DNS problem on my end, for sure, but I temporarily fixed it by manually putting in my ISP's DNS server IP addresses in the connection properties of all my LAN systems (instead of using the NAT box's IP and forwarding DNS). The problem was permanently fixed - I don't know how - when I moved to a Linux-based NAT system. 😉
FWIW, I haven't been having any problems on my end recently, but will keep an eye out for them...