Tarde, mas vou postar meu caso como diferente de todos os itens acima.
No meu caso, /etc/resolv.conf é um link simbólico para /var/run/NetworkManager/resolv.conf , e por alguma razão cat /etc/resolv.conf me dá erro em nenhum arquivo ou diretório (talvez porque esteja vazio?)
Se eu abri-lo com o vi e adicionar nameserver x.x.x.x , ele é limpo na reinicialização.
Eu tentei editar /etc/network/interfaces , adicionar dns-nameservers x.x.x.x , alterado /etc/dhcp/dhclient.conf e removido em request domain-name-servers , também editado prepend domain-name-servers x.x.x.x .
O binário Resolvconf não está instalado, NetworkManager.conf não tem nada relevante. Mas toda vez que eu reiniciei a máquina, não havia servidor de domínio.
Não sei qual é a razão, mas parece ter a ver com o fato de que esta é uma máquina VBox, iniciada pelo GNS3 e por causa dessa configuração dentro do VBox, eu tenho que deixá-la sem nenhuma interface criada. Aparentemente, o GNS3 cria uma "interface UDP" quando eu inicio a máquina, desde que eu a inicie pelo GNS3.
Então, para evitar que eu procurasse infinitamente, eu adicionei echo nameserver x.x.x.x> /etc/resolv.conf a /etc/profile , problema resolvido (não resolvido, mas trabalhado em torno de hehe). Mas pode ser interessante saber o que acontece com esse cenário, se alguém o encontrar.