Workstations falling of network

I administer a network of around 89 PC’s using MS-DNS running under win2k server and DHCP running under the a sonic wall system.

We changed network providers around 2 months ago and since then various PC’s on the network fall off the lan. I have to ipconfig /flush then delete the records from the DNS server, then reboot the client to get them back on.

its not every PC just around 3-4.. they loose access to named shared drives, when they ping an interal server by name, it will return an outside ip address.

This really is driving me nuts DNS is not reporting any errors