A maneira como geralmente vejo isso é fazer com que o servidor DNS resolva apenas o FQDN, mas adicione o domínio à lista de pesquisa na configuração DNS dos clientes. Você pode enviar isso para os clientes via DHCP. Eu tenho duas redes sendo executadas dessa maneira e isso simplesmente funciona, sem problemas no Windows, Linux ou Mac.