The NN is compiled by the Computer Browser service (and yes it has always been crap!)
The basic idea is that computer browser compiles a NetBIOS list of all machines by broadcasting on the local segment.
Everytime a PC starts up, or several other events, it triggers an election process where all the machines on the same segment decide on a Segment Master Browser and Backup (among other things)
The machine then becomes responsible for compiling the list and distributing it, but also for contacting all the other Segment Master Browsers to exchange/merge lists with them to see what is going on outside the segment - remember, you can't broadcast outside a segment so you need one of these for each segment. Then there is a "Domain" Master Browser, that consolidates for a domain and exchanges lists with other domains. Not sure how that works in workgroups.There are other things like which network agents you have you stack that effect how many browsers there are and what they are responsible for. But pinging isn't involved and won't fill in your browse lists. Perhaps start by checking your network stack has all the same components as your other PCs and the same version/SP of Windows, then add it to a different workgroup, reboot, add it back, reboot. Might help