Are you seeing EVENT ID 8003 errors in event viewer on your servers? In a segmented network, you may be having Master browser Election problems (forced elections). This is very common in a routed environment. The problem with forced elections is that a 9x machine may take over browsing roles. This can cause problems. 9x machines have a limited cache size for maintaining the browsing list. If the number of computers in your environment takes up more space then the 9x machines can handle, you will have an incomplete browse list.
The first step it to look for Event ID 8003 errors on your servers (system log).
Next, I would use resource kit tool BROWMON and BROWSTAT
to determine who is the master browser. (Browstat -status)
You could also check your WINS database to see who is master browser (Check in wins "BH" = Domain Master Browser )
Really need more details about your specific problem. But a common mistake is to forward UDP broadcasts on routers.
I am most familiar with Cisco routers. There is a feature called IP Helper. Many people turn this on so that DHCP broadcasts can be passed through routers. However, they fail to realize that when they turn on IP Helper, the default configuration will also all UDP Netbios broadcasts to pass through routers. On a Cisco swith, you must manuall turn off port 137 and 138. This may solve your problem too..
Here is more information:
From what I read, if IP an Helper address is spcified and UDP forwarding is enabled, many different types of broadcast packets are forwarded by default (ports 37, 49, 53, 69, 67, 68, 137, 138).
The documentation suggests that ports 137 and 138 should be disabled. This will allow the brower service to function as it was designed.
These are the Technet Articles I referenced:
-Hope this helps.. Joseph L. Poandl
MCSE 2000