XP SP2 and DNS issue

I have a problem with all of my XP SP2 machines. All are accessing an W2K Domain and W2K DNS and DHCP servers. The problem is that when a PC is started in the morning DNS works fine. If I need to restart the PC then it can no longer find the DNS server. The two things that seem to work if I need to restart a PC is to shutdown and wait 5-10 minutes and then start the PC again, or I can start the PC and do ipconfig/release & ipconfig/flushdns and then restart and everything is fine. This is not a solution so and help is appreciated.