Então, no final, a única coisa que funcionava era desligar o Perfil Privado do Firewall do Windows.
Antes de fazer isso, modificamos as configurações (incluindo desabilitando o NetBIOS ) para que não houvesse tráfego sendo descartado (naquele perfil), de modo que ter o perfil desligado era praticamente o mesmo que tê-lo ativado. Nós monitoramos por vários dias antes e depois para ter certeza disso também.
(Tentamos permitir a entrada por padrão, e ela ainda bloqueou 135, então desativamos todo o perfil.)