Eu resolvi esse problema com dois roteadores diferentes (Draytek e Billion), mas não tenho certeza sobre a causa raiz. Eu acho que a solicitação de DNS sendo "proxied" através do roteador adiciona o suficiente para um atraso de tempos limite esporádicos.
O que eu fiz foi configurar o DHCP para fornecer a cada cliente as configurações de DNS, em vez de usar o roteador como o servidor DNS.
Aqui, no meu Bilhão, eu desmarcou "Usar roteador como servidor DNS" e deixar o DHCP atribuir os servidores: