How to Permanently Configure DNS Server List in Ubuntu 16.04

To get the D-Bus controlled dnsmasq that NetworkManager runs to use different DNS servers, there are the following options (obviously adjust domains and IP addresses in the examples):

• Add a file to /etc/NetworkManager/dnsmasq.d that sets the DNS server for the subnet you want: myvpn-server.conf could contain server=/myvpn.domain.com/10.8.4.9. This will always be respected by dnsmasq even when not connected to the VPN, in which case queries for these domains should time out. Disadvantage is that you need to specify the IP address statically, advantage is simplicity
• Use D-Bus to talk directly to dnsmasq to tell it to update the servers using something like sudo dbus-send --system --print-reply --dest=org.freedesktop.NetworkManager.dnsmasq /uk/org/thekelleys/dnsmasq uk.org.thekelleys.SetDomainServers "array:string:192.168.0.1,/myvpn.domain.com/10.8.4.9". This could be scripted when the vpn connects. You'd need to look up existing DNS servers (the 192.168.0.1 in my example) over D-Bus or using nm-cli
• Use D-Bus to talk to Network Manager itself and tell it to update the servers. Here's an example of doing this using Python which would require some work to include the current servers.

I'm using the first option and have only tried preliminary versions of the other two

From the above output, it looks like Ubuntu is trying to use a local DNS server. Correct? Is it caching a failed lookup on my local machine?

Yes, Ubuntu is using whatever was provided with dhcp lease, more specifically dnsmasq, a plug-in, that takes care of that for network-manager.

Is Ubuntu using this second DNS server sometimes? Why? Is it load balancing? Is the local one slower?

If the first dns fails to resolve, then dnsmasq should redirect the query to the secondary dns. At least that's the idea.

In case you'd like to use your own dns-server Personally, I always use supersede domain-name-server xxx.xx.xxx.xxx in /etc/dhcp/dhclient.conf to tell my Ubuntu system to replace whatever dns it receives via dhcp lease with my own server. Here's the excerpt from that file:

30)serg@ubuntu[/home/xieerqi]
>_ cat /etc/dhcp/dhclient.conf                                                 
# Configuration file for /sbin/dhclient, which is included in Debian's
#   dhcp3-client package.
#
# This is a sample configuration file for dhclient. See dhclient.conf's
#   man page for more information about the syntax of this file
#   and a more comprehensive list of the parameters understood by
#   dhclient.
#
# Normally, if the DHCP server provides reasonable information and does
#   not leave anything out (like the domain name, for example), then
#   few changes must be made to this file, if any.
#

option rfc3442-classless-static-routes code 121 = array of unsigned integer 8;

#send host-name "andare.fugue.com";
send host-name = gethostname();
#send dhcp-client-identifier 1:0:a0:24:ab:fb:9c;
#send dhcp-lease-time 3600;
#supersede domain-name "fugue.com home.vix.com";
supersede domain-name-servers 208.67.220.220;
#prepend domain-name-servers 127.0.0.1;
request subnet-mask, broadcast-address, time-offset, routers,
    domain-name, domain-name-servers, domain-search, host-name,
    dhcp6.name-servers, dhcp6.domain-search,
    netbios-name-servers, netbios-scope, interface-mtu,
    rfc3442-classless-static-routes, ntp-servers,
    dhcp6.fqdn, dhcp6.sntp-servers;

After setting that up and reconnecting or restarting network-manager, here's what I have:

31)serg@ubuntu[/home/xieerqi]
>_ nmcli dev list | grep -i dns                                                
IP4.DNS[1]:                             208.67.220.220

Nslookup will report Server: 127.0.1.1 and Address: 127.0.1.1#53 since it is Network-Manager's dsnmasq that listens on that address, and it uses whatever was provided by dhcp ( in this case , the substituted dns)