Você está exatamente certo: a funcionalidade de "navegação" do Windows sendo baseada em pacotes de transmissão e sua VPN não encaminhando pacotes de transmissão através de limites de sub-rede.
Geralmente, encaminhar as transmissões da camada 2 na camada 3 não é desejável. Seu produto VPN particular pode permitir que você configure o encaminhamento de transmissão NetBIOS. Como alternativa, você pode verificar a implementação de um servidor WINS em cada lado da VPN para permitir que os clientes "navegar".
Estou com @joeqwerty nisso, até certo ponto. Implemente uma metodologia estruturada para a localização de recursos em sua organização e você obterá os benefícios no futuro.