Network/Server Connection

I am having a problem were a PC looses network connection to some servers. You can see the server in Network Neighborhood. The main servers are the Exchange 5.5 and the Lotus Notes servers. The error is server not found. We use DHCP to assign IP addresses. If I run ipconfig/release and ipconfig/renew the connection is good again. I do not have the problem with the static machines. I have installed another DHCP server with no help. I have made changes to the options in DHCP with no help. My network uses Win2000 Controllers only. The systems having the problems are mainly Win 2000 pro but I have seen some NT 4.0 system have the same problem. I also have a WINS server on the Network.