I'm going to make an assumption here because this sounds like a very typical browsing issue. I'm going to assume at least some of your Windows9x computers (like all your 98SE machines perhaps) have file & print sharing enabled. If so its very likely that they are maintaining inacurate browse lists.
You need to ensure none of your Windows9x machines can become Master Browsers. First off, if you have no need to have these services enabled, I'd recommend removing the "File and Print Sharing Service for Microsoft networks" under network properties. This service just takes up memory and introduces problems like what you are describing. If this is not feasable (you need to share that inkjet printer on the windows9x parallel port that your boss just loves to use), you can disable just the ability to maintain browse lists. If you go to the network settings, highlight "File and Print Sharing Service for Microsoft networks" and select properties you will see a value called "Browse Master". By default this is set to "Automatic". If you set this to "Disable" this machine will no longer attempt to become a Master Browser.
What this means in short is that only your w2k server will maintain the Browse List (Network Neighborhood) for your entire network.
mdsnitc@sandia.gov