Warning: My memory on this is a little fuzzy...
I had a Win95B machine that was visible to only some XP and 2k machines in the same Workgroup, and vice versa, but it was never consistent. I never could figure out what the problem was. Eventually it got to the point that the Win95B machine was invisible to most of the network. Installing just about every networking protocol on the Win95B machine helped for a while, but that didn't resolve the problem. I gave up and just had TCP/IP and NetBIOS on the Win95B machine, accepted that it wouldn't be a full member, and recently replaced it with a Win2k PC.
We had a related problem recently where Win2k and XP machines weren't consistently visible in the same Workgroup. Someone eventually surmized that there was some battle between which PC on the network was going to be the Master Browser (IIRC), and it was somehow solved. I know even less of the details in that case.
I think there's some sort of problem with the communication between the Win9x and 2k+ machines that eventually will bite one. The best solution seems to be to replace the 9x machines. But MS wouldn't make them incompatible on purpose, naaaah...
I hope this helps tickle a solution for you. Luck!
Cheers,
Scott.