To help isolate the problem, use the traceroute (Linux or OS X) command, which on a Microsoft Windows system is tracert. Issue the command when the DNS issue is occurring and when it is not. I.e., tracert -d 62.117.1.25 to check the network path to the DNS server. That will show you all of the network hops between your system and the DNS server and, if there is a problem reaching the DNS server initially, where the problem is occurring. The "-d" option for tracert instructs it to not attempt to resolve IP addresses to domain names, which won't work initially. You can omit the -d option when DNS is working.
You could also, try changing the DNS server for the nslookup command when you run it immediately after boot to help isolate the problem. Since 8.8.8.8 is a Google DNS server, see what happens if you specify it be used. E.g.: nslookup heise.de 8.8.8.8. If you put an IP address of a DNS server at the end of the command, that DNS server will be used instead of the one Windows is configured to use. Alternatively, you can just type nslookup and then at the nslookup prompt type server 8.8.8.8. E.g.:
c:\>nslookup
Default Server: UnKnown
Address: ::1
> server 8.8.8.8
Default Server: google-public-dns-a.google.com
Address: 8.8.8.8
> heise.de
Server: google-public-dns-a.google.com
Address: 8.8.8.8
Non-authoritative answer:
Name: heise.de
Addresses: 2a02:2e0:3fe:1001:302::
193.99.144.80
If you use the Google DNS server initially, does the problem still occur or do you, instead, get a reply from that DNS server?
I've used DNSQuerySniffer created by Nir Sofer, which is free and available from his NirSoft website along with many other free utilities he has created, for investigating DNS issues on Windows systems. You could use it to aid in troubleshooting the issue. E.g., you could use it to verify your system is sending out the DNS queries when the problem is occurring.
You could also test to see whether changing the timeout value for nslookup makes any difference. E.g., to change it from 2 seconds to 4 seconds you could get the nslookup prompt, by just typing nslookup at a command prompt without following it by an IP address or fully qualified domain name (FQDN) and then type set timeout=4. Another parameter you can adjust for nslookup is the number of retries, which can be changed with set retry=X where X is the number of times to retry. E.g.:
c:\>nslookup
Default Server: UnKnown
Address: ::1
> set timeout=4
> heise.de
Server: UnKnown
Address: ::1
Non-authoritative answer:
Name: heise.de
Addresses: 2a02:2e0:3fe:1001:302::
193.99.144.80
>
The change to a value, such as the timeout value, isn't permanent, it only applies to that instance of nslookup. Once you type exit to quit the nslookup command, the next time you use the command, you will have the default value of 2 seconds again.
Update: To determine if there is a network issue somewhere along the network path between your Windows system and the DNS server you are using, you could run some tracert tests, e.g., tracert ns1.telecolumbus.net or tracert -d tracert ns1.telecolumbus.net to forego DNS resolution for the tracert command. Tracert might show a problem somewhere else along the network path. E.g., you might see high round-trip times (RTTs), or a consistent delay at a particular network hop, etc.
You could also try changing the DNS server you are using to another one, e.g., the Google DNS server at 8.8.8.8, or use OpenDNS servers, e.g., 208.67.222.222 and 208.67.220.220 - see What are the pros and cons of using an alternative DNS instead of the ISP DNS server?. You could make the change at the Windows system itself; if it is obtaining an IP address via DHCP now, you could modify the configuration of the network adapter on the Windows system to use a static IP address and DNS server, instead or, if your router is functioning as a DHCP server, you could configure your router to provide a Google or OpenDNS DNS server IP address for the DNS server that devices on your local area network (LAN) will use. Then check to see if the problem remains or no longer exists.
