Let me get into a bit of detail for the tack I'm taking here...
All computers on a network have an IP address. And assuming you can see a machine by IP, there is likely not a firewall issue. The Shared computers section of the Finder window (and Network Neighborhood/My Network Places/Network window in Windows) displays computer names that are discovered using NetBIOS broadcasts on small networks. I think what's not happening here is that the Mac isn't picking up on the NetBIOS broadcast. This is usually related to the Mac not being in the same workgroup. Even if the Mac's software firewall is turned on (it is not, by default), it should still see those broadcasts. Even if the Mac isn't configured for File Sharing (i.e. sharing its files out to other machines), it should still see those broadcasts.
I don't have sharing of any kind enabled on my MBP, and the Firewire is as tight as a snare drum, with Stealth Mode turned on, and I can still see my PCs and NAS which is using SMB.
Now, I do have a DNS entry set up for my NAS that manually resolves its static IP. But that's the only difference I can think of, aside from the config of the router. I don't believe it's the router blocking broadcasts because the Windows machines can browse each other.
It might not be a bad idea to install Bonjour on the Windows machines as that uses UPNP and should handle name resolution using its own protocols. That would be my next step (at least on a trial basis on one of the Windows machines).