In a mixed environment check your protocol stacks, I bet the default is not the same on all machines, and the stack order could also be causing part of the issue. Also make sure that the same protocols are installed and properly configured on each machine. You may also want to remove any protocols that are not being used, or that are broadcast based... IE: NetBEUI. Also take a look at how many PC's can be seen, there is a limit to how many will be shown on the network neighborhood screen. See if the amount of computers shown is consistent... in other words do all computers show 25 pc, even if they are a different 25? If that is the case, you can even look for bad or high traffic network segments that may inhibit "seeing" other PCs properly.
Hopefully this gives you some things to check, and maybe even a resolution.
Good Luck,
SteelDragon