PC Does not Appear on Network in Win2k: Help!

Hey everybody! I'm sick of this problem, and there have been other assorted techs and enthusiasts who have failed to resolve it. It stymies my limited knowledge.

My father has a 1x PC and 1x Laptop. They are both Win2k-SP4. They are connected to a wired router, which is in turn connected to a cable modem (for Roadrunner).

Both the PC and the LAP access the internet fine.

They are set up on the LAN as follows (both settings are identical for the PC & LAP unless otherwise noted):
1. Both have standard pc names and use the workgroup 'WORKGROUP'.
2. Both have TCP IP enabled (SUDDEN MASSIVE KEYBOARD ERROR<CONTINUE IN REPSONSE)
 
Sorry about that -- I'm not sure what happened. Continued.

2. TCP/IP is enabled. Automatic DNS identification has also been enabled.
3. NetBUI is enabled (because we can't get any network identification of either PC or LAP without it).
4. I can ping the LAP by name or IP address from dos. Contrariwise, I can ping the PC from the LAP. I cannot remember the command that you run from 'Run program' than allow you to attempt to access a remote harddrive by pc name or IP address (so I haven't tried this).
5. To keep all simple, the firewall (8Signs on both machines) has been turned off.

Those are the main circumstances. I have updated the ethernet drivers on both machines. Both access the broadband fine. According to ping, both PC and LAP are accessible by TCP/IP.

CRUX:
--ON PC, when I explore Entire Network> Microsoft Windows Network> WORKGROUP> I find neither PC by name nor LAP.
--ON LAP, when I explore Entire Network> Microsoft Windows Network> WORKGROUP> I sometimes do not find LAP by name. When LAP does not appear, no amount of re-exploring the network will find anything (I assume the auto DNS locator holds the wrong settings in cache until the machines are rebooted and exploring is reattempted).
-- ON LAP, when I explore Entire Network> Microsoft Windows Network> WORKGROUP> I sometimes find the LAP by name. THEN when I try to explore WORKGROUP from PC, I find LAP and the two machines can share directories, printers, etc. Again, however, this is not consistent.
--I NEVER FIND PC BY NAME IN WORKGROUP, WHETHER I AM BROWSING FROM PC OR FROM LAP.

-- I have not assigned static IP addresses to these machines, because they do not seem to access the broadband when I attempt this. If I could get the broadband to work with fixed IP addresses, that is probably what I would do.

Probably a case of too much information, but I am trying to be thorough. All you suggestions are entirely welcome and actively solicited. Thanks all!
 
Just a musing:

As the PC never shows up in network neighborhood, should I try uninstalling and then reinstalling the nics and networking services for it? Could it be that networking services are somehow injured?
 
Yes Roadworker, that's the wild thing: Windows DNS assigns them a 'temporary' ip address, but they ping just fine. I can also ping the computer names, each to the other.
 
Top