Environment

Two small networks connected via a hardware VPN that is established by two identical Netgear FVS318 routers. 

Problem

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.

Troubleshooting

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:

How To Diagnose and Test TCP/IP or NetBIOS Network Connections in Windows Server 2003

This article points out that ports 137 and 138 must be open for NETBIOS over TCP/IP to work:

How to configure a firewall for domains and trusts

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.

Solution

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.