Проблема решилась.
Какого-то фига Network Manager подумал что он умнее меня и каждый раз прописывал в /etc/resolv.conf DNS адреса моего провайдера.

Решилось правкой конфига NM: /etc/NetworkManager/NetworkManager.conf

[main]
plugins=ifupdown,keyfile
dns=none
rc-manager=unmanaged

Правкой /etc/resolf.conf на сервера на 8.8.8.8, 8.8.4.4

И перезапуском сервиса:
sudo service NetworkManager restart

Больше российский провайдер в списке DNS не появлялся.