A resposta acabou sendo brutal e simples. O cliente DHCP estava substituindo as entradas de DNS em /etc/dhcp/dhclient.conf
via supersede domain-name-servers ...,...;
. Eu não tenho idéia do porque estava lá, eu devo ter esquecido que eu coloquei isso há um tempo.
O comando que me salvou:
sudo find /etc -type f -print0 2>/dev/null | xargs -0 sudo grep "<hardcoded address>"
Sim, simples assim.