Windows 7: Win Explorer does not show all computers on network

I have a DSL modem/wireless router with three PCs connected via Wi-Fi. The router is connected to a hub with a cable. Two additional PCs are connected to the hub via cable. Sometimes (but not always) when I restart my Wi-Fi connected laptop and launch the Win Explorer it 'sees' the other Wi-Fi connected PCs, but not the two cable connected PCs. I have tried turning network discovery on and off and rebooting, but that does not always resolve the issue.
I can enter \\device name in the Win Explorer address line and it will show all the shares on the entered device. However, if I shut down the Explorer and relaunch it, that device still does not show in the network list.
I don't use Home Groups and all PCs are members of the same Workgroup. My laptop runs Win 7 Starter, my wife's runs Win 7 Home Premium (and sometimes has the same problem), and the third Wi-Fi connected PC is our Home Theater PC running Win 7 Home Premium (it is currently having the same problem). The two cable connected PCs are a laptop running XP Home and our Windows Home Server.
Any ideas on how I permanently resolve this problem?

If the machines are always accessible via \\DeviceName\ an easy fix would be to create a folder on the desktop with shortcuts to \\DeviceName(s)\ for each networked machine.

Not a fix but a simple workaround.

Thanks for the thought, but I am looking for an explanation as to how this happens and information on how to prevent it from happening again. I know your work around would be the easier way, but this bugs me and inquiring minds want to know.

Update - I disabled the LAN adapter on the XP laptop and connected it with Wi-Fi. My Win 7 laptop still does not 'see' the XP laptop. I am beginning to believe that Win 7 PCs have a problem 'seeing' XP derivative PCs sometimes. I have rebooted my Win 7 laptop a few times since my first post in this thread and the two XP derivative PCs have not yet shown up.

This is commonly reported, although my Windows 7 machine can "see" my wifes XP netbook. I connect to the router by CAT5 and she is using wireless G. I do have her in a homegroup though and we are in the same workgroup.

How did you get her in a Homegroup? My computer says only Win 7 computers can participate in Homegroups.

Yes that's true, what I mean to say is that I do have my machine as part of a homegroup, although I just access her netbook through "Network" in windows Explorer. It's visible if it's on and it's not when it's not.

I have an account on her machine with the same user name and password.
I have Network discovery on
I have file and printer sharing on
I have read/write to public folders allowed
I have 128bit encryption on
I have password protected sharing on
I allow windows to manage the homegroup settings (the only thing checked for homegroup use is "printers")

My settings are the same as yours except that I don't have public folder sharing turned on and don't have a Homegroup. Just for grins I did a Shutdown rather than a Restart on my Win 7 laptop. When I powered back up again the Windows Home Server was back in the Network list but the XP laptop (that I had changed from cable connected to Wi-Fi connected as an experiment) was not. I had not changed any of the Advanced Sharing Options.
I just checked the Home Theater PC (Win 7). It had been Restarted because of updates. The Windows Home Server is back in its Network list but the XP laptop is not. Guess I'll change the XP laptop back to cable connection and see if it reappears.
This is what drives me crazy. The problem seems to be random and arbitrary. It must have something to do with whether or not I am wearing socks when I restart my laptop.

Yep, after I changed the XP laptop back to a cabled connection it reappeared in the Network list on my Win 7 laptop.