You know what? I have the same exact problem at my work too. I'm the maintenance / in-house tech support there and I have been trying to find an answer for the longest time. What I found to work temporarily is instead on doing a full restart, you can disable the networking, and then re-enabling the network. This process takes only 10 - 15 seconds, and afterwards, you can see it on the network again. At first I thought it was an issue with the network cable, but after seeing that someone else has this problem (I tried several different cables), the cable is no longer a suspect. We have a Windows 2000 server as a BDC (backup) to an NT 4 Primary.