Parece que systemd-resolve é responsável por atualizar essas linhas da resposta obtida do DHCP.
O problema encontrado é que, para hosts nos domínios listados na diretiva search , ele falhará se o sistema estiver mal configurado.
No meu caso, não consegui identificar o motivo exato da falha, mas um dpkg-reconfigure resolvconf como sugerido por link resolveu o problema para mim.
Observe que, no meu caso, o link /etc/resolv.conf não foi alterado pela reconfiguração, mas algo mais deve ter mudado e resolvido o problema para mim.