Network Connection Problem

I am having a problems with PCs looses network connection to some servers. Mainly my Remedy Server and Exchange server. You can see the servers in Network Neighborhood. The error is server not found. We use DHCP to assign IP addresses (12 day lease). I have tried different lease periods with no help. 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 Domain Controllers only. The systems having the problems are mainly Win 2000 but I have seen some NT 4.0 system have the same problem. I also have a WINS server on the Network.