Проблема решилась.
Какого-то фига 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 не появлялся.