Funcionou. O Windows adiciona um sufixo de domínio no final das consultas, portanto, ele estava realmente solicitando mithrandir.companydomain.com
(dentro de uma empresa onde todas as estações de trabalho são colocadas no domínio company.com).
Depois disso, o windows tentou o mithrandir.com, que foi para a rede mais ampla e voltou como inexistente.
Não sei como resolver o problema, mas pelo menos eu sei que é um problema com a estação de trabalho do Windows e não com a minha configuração do dnsmasq.