Two small networks connected via a hardware VPN that is established by two identical Netgear FVS318 routers.
User has always been able PING remote machines from XP and Vista machines using the remote machine names. Pinging from the XP machine stopped working, although pinging from Vista still works. Pinging the IP address still works.
On the XP machine, in the TCP/IP Properties, NETBIOS over TCP/IP is enabled.
I tried some of the NBTSTAT commands in this article but could only confirm that the local XP computer didn't know about the machine names on the remote network:
This article points out that ports 137 and 138 must be open for NETBIOS over TCP/IP to work:
I checked 137 and 138 on the remote machine's firewall and they were in fact open to receive traffic from to the local machine's subnet.
Finally I turned on XP firewall success and failure logging on the remote machine, then pinged it from the working local Vista machine. In the firewall log, I noticed that the remote machine was sending a UDP packet on port 137 to the local Vista machine.
I recalled that I had recently updated group policy on the local network to disallow the File and Printer Sharing Exception (which includes ports 137 and 138) from the remote network. I was thinking that I didn't want people in the remote office to access files on the local network.
Once I changed the File and Printer exception in the local network's Group Policy to include both the localsubnet and the remote subnet, NETBIOS over TCP/IP started working again. I guess I'll just have to trust the passwords on the local network to prevent unauthorized browsing from the remote network.
In summary, the “trick” was to realize that when sending a NETBIOS over TCP/IP request, the local machine must be able to receive UDP packets on port 137.