You will need to describe your network environment.
For example, here at my home I have a WIFI router that connects to the internet. All of my PC's and test VM's use DHCP. When the PC boots, DHCP acquires an IP address from the router. The NIC's are set to "Register this connections address in DNS". When I run NSLOOKUP against a name or IP address, it displays the PC's IP or it's name. All of my PC's use the WIFI router as the DNS server. (The default from DHCP.)
There was a third party on this trying to install software from the server and then I now have this issue. I am not sure what they did and do not know what they might have changed.
Your server/desktop/network admin should have been looking over their shoulder to watch what they were doing and verify that the decisions that they made were consistent with your organizations polices and help them work through any issue that they might encounter.
Is this a home network? Small business network? Do you use Active Directory? Who provides desktop and server support? Have they investigated this problem? What DNS servers do your machines use?