Comment 22 for bug 1671606

Okay so since resolvconf and dmasq are not cooperating, I have resorted to using dnscrypt-proxy. Credit to QkiZ, the dnscrypt-proxy service works EVERY TIME and ignores the (completely broken) DNS resolution of dnsmasq and resolvconf. Even with the newest version of network-manager (1.2.6) on 16.04 LTS and all its dependencies:
 network-manager
 libnm-glib-vpn1
 libnm-glib4
 libnm0
 libnm-util2
No more DNS resolution issues!
To apply this workaround (which actually also offers some security benefits against DNS leakage), use:
sudo apt install dnscrypt-proxy
In the network manager, select "Edit Connections", select the primary (non-VPN) network you use, click on the "IPv4 Settings" tab, change the "Method" tab to "Automatic (DHCP) addresses only", then add 127.0.0.2 to the "DNS servers:" box. Save your changes, then restart the connection by disabling and enabling networking. Now go to https://www.opendns.com/welcome/ and you should see a nice check mark.
Now, your network connection and VPN should work (meaning DNS resolution won't break on you) every single time you wake up from suspend or use
sudo service network-manager restart
And if for some odd reason it's slow just restart the network manager repeatedly by aliasing that to something like
alias nm-restart='sudo service network-manager restart'
in your ~/.bash_aliases file. I know, annoying but at least DNS resolution actually works and the computer doesn't have to be literally restarted to connect to the internet.
This isn't intended to be a fix, just a possible alternative for those of us who experience total DNS resolution failure using a vpn on Ubuntu.