OK, depois de algum esforço, está resolvido. Eu me sinto um pouco estúpido, mas vou compartilhar no caso de ajudar alguém.
Corri nbtstat -a PCNAME
em todos os computadores e notei uma linha __MSBROWSE__
em mais de um.
Demorei um pouco para descobrir, mas aparentemente um dos computadores tinha uma máscara de sub-rede incorreta de 255.0.0.0 em vez de 255.255.255.0. Isso leva a vários navegadores mestres e a todo tipo de confusão.