Se você quiser que as máquinas linux pesquisem automaticamente sufixos dns, seu servidor DHCP precisará emitir a opção "domain-name" preenchida com os sufixos que você deseja anexar a nomes de domínio não qualificados (onde você apenas declara a parte do host) . A diretiva do escopo do servidor isc-dhcp seria:
option domain-name "company.com";
É provável que suas máquinas com Windows estejam recebendo o sufixo primário de um membro do domínio.
Se você não estiver usando o dhcp, poderá adicioná-lo manualmente ao seu /etc/resolv.conf :
domain company.com