Rastreando as coisas com o wireshark, descobriu-se que a VPN estava empurrando os servidores DNS do OpenDNS, que nunca retornavam "não encontrados". O cliente samba do Linux estava fazendo uma pesquisa de DNS antes de uma consulta de NetBIOS, e assim "encontrava" as máquinas nos servidores do OpenDNS "sem domínio aqui" em vez da rede local.
Alterar as configurações de DNS da VPN para usar os servidores DNS do Google, em vez disso, resolveu o problema, assim como a alteração da configuração do Samba para evitar pesquisas de DNS, adicionando
name resolve order = wins lmhosts bcast
dns proxy = no
para /etc/samba/smb.conf