Nope, same results unfortunately. I have tried basically everything:

noctua@corinth:~$ nmcli c
NAME      UUID                                  TYPE             DEVICE 
Bn80rrF8  11d6931f-8d5b-4f47-8a1e-38f33117811b  802-11-wireless  wlo1   
US-East   cf291340-3c52-4347-8ce9-e609bdecec32  vpn              wlo1   
tun0      2476d73d-a1b6-4b0f-adf3-552bd095d38a  tun              tun0   
tun0      0058ff81-1d38-4d8b-a486-a29619bb7b99  tun              --     
tun0      56ca187e-67bb-438e-b20a-9ed44c223619  tun              --     

Here's where I try every possible way to apply 'ipv4.dns-priority -42'

noctua@corinth:~$ sudo nmcli connection modify uuid  ipv4.dns-priority -42
0058ff81-1d38-4d8b-a486-a29619bb7b99  56ca187e-67bb-438e-b20a-9ed44c223619
11d6931f-8d5b-4f47-8a1e-38f33117811b  cf291340-3c52-4347-8ce9-e609bdecec32
2476d73d-a1b6-4b0f-adf3-552bd095d38a  
noctua@corinth:~$ sudo nmcli connection modify uuid 0058ff81-1d38-4d8b-a486-a29619bb7b99 ipv4.dns-priority -42
noctua@corinth:~$ sudo nmcli connection modify uuid 56ca187e-67bb-438e-b20a-9ed44c223619 ipv4.dns-priority -42
noctua@corinth:~$ sudo nmcli connection modify uuid 2476d73d-a1b6-4b0f-adf3-552bd095d38a ipv4.dns-priority -42
noctua@corinth:~$ sudo nmcli connection modify uuid cf291340-3c52-4347-8ce9-e609bdecec32 ipv4.dns-priority -42
noctua@corinth:~$ sudo nmcli connection modify tun0 ipv4.dns-priority -42noctua@corinth:~$ sudo nmcli connection modify US-East ipv4.dns-priority -42

And then I tried reactivating the connection each time successfully through the GUI and then through nmcli, for example:

noctua@corinth:~$ sudo nmcli connection modify US-East ipv4.dns-priority -42
noctua@corinth:~$ sudo nmcli connection down US-East 
Connection 'US-East' successfully deactivated (D-Bus active path: /org/freedesktop/NetworkManager/ActiveConnection/10)
noctua@corinth:~$ sudo nmcli --ask connection up US-East 
A password is required to connect to 'US-East'.
Password (vpn.secrets.password): 
VPN connection successfully activated (D-Bus active path: /org/freedesktop/NetworkManager/ActiveConnection/12)

I even tried:
noctua@corinth:~$ sudo nmcli connection reload tun0
noctua@corinth:~$ sudo nmcli connection reload US-East

But every single time, I still I get the same results testing for DNS leaks, that DNS queries are clearly being sent to my ISP (Verizon in this case). So...this doesn't appear to work :( 

I think the only real solution here to stop DNS leaks over NM-VPN connections is to provide an option to specify the routing-only domain or make "." a valid search domain name on systems that force the use of systemd-resolved (so...basically every major Linux distro including those based off Ubuntu, Arch Linux, AND the upcoming release of Debian Stretch). This is a rather serious problem, hence the kinda hackish patch I made forcing the systemd-resolved method SetLinkDomains to accept the routing-only domain ".". Ultimately, I think there needs to be the OPTION to specify the routing-only domain to prevent DNS leaks. 

All those posts on the original launchpad thread, the Arch forums, and various duplicate bug threads of the original launchpad bug https://bugs.launchpad.net/ubuntu/+source/network-manager/+bug/1624317 where users put the line 'dhcp-option DOMAIN-ROUTE .' in client openvpn config files in conjunction with the (now available in several package repositories) update-systemd-resolved script at https://github.com/jonathanio/update-systemd-resolved all amount to basically the same thing I did with my less-than-optimal patch: calling the systemd-resolved API method SetLinkDomains using the routing-only domain ".". So I think supporting this is very important indeed. 

Even more simply, "." could be allowed/parsed as a valid search domain when reading the dns-search line of a config file in /etc/NetworkManager/system-connections/<con-id> containing something like
[ipv4]
dns=209.222.18.222;209.222.18.218;
dns-search=.;
ignore-auto-dns=true
method=auto

I am positive that domains otherwise considered 'valid' ("." or "~." don't appear to be allowed, see above posts) are passed to SetLinkDomains. For example, if I set dns-search=bogusdomain; in the config file (or through the GUI) I end up with the following:

noctua@corinth:~$ sudo cat /etc/NetworkManager/system-connections/US-East 
[sudo] password for noctua: 
[connection]
id=US-East
uuid=cf291340-3c52-4347-8ce9-e609bdecec32
type=vpn
permissions=user:noctua:;
secondaries=
timestamp=1497394667

[vpn]
auth=SHA1
ca=/home/noctua/Documents/openvpn/openvpn-legacy-tcp/ca.crt
cipher=BF-CBC
comp-lzo=yes
connection-type=password
dev=tun
dev-type=tun
password-flags=1
proto-tcp=yes
remote=us-east.privateinternetaccess.com:443
remote-cert-tls=server
reneg-seconds=0
username=<my username here>
service-type=org.freedesktop.NetworkManager.openvpn

[ipv4]
dns=209.222.18.222;209.222.18.218;
dns-priority=-42
dns-search=bogusdomain;
method=auto

[ipv6]
addr-gen-mode=stable-privacy
dns-search=
ip6-privacy=0
method=ignore


Now notice the line under tun0 that says 'DNS Domain: bogusdomain'

noctua@corinth:~$ systemd-resolve --status 
Global
          DNSSEC NTA: 10.in-addr.arpa
                      16.172.in-addr.arpa
                      168.192.in-addr.arpa
                      17.172.in-addr.arpa
                      18.172.in-addr.arpa
                      19.172.in-addr.arpa
                      20.172.in-addr.arpa
                      21.172.in-addr.arpa
                      22.172.in-addr.arpa
                      23.172.in-addr.arpa
                      24.172.in-addr.arpa
                      25.172.in-addr.arpa
                      26.172.in-addr.arpa
                      27.172.in-addr.arpa
                      28.172.in-addr.arpa
                      29.172.in-addr.arpa
                      30.172.in-addr.arpa
                      31.172.in-addr.arpa
                      corp
                      d.f.ip6.arpa
                      home
                      internal
                      intranet
                      lan
                      local
                      private
                      test

Link 16 (tun0)
      Current Scopes: DNS
       LLMNR setting: yes
MulticastDNS setting: no
      DNSSEC setting: no
    DNSSEC supported: no
         DNS Servers: 209.222.18.222
                      209.222.18.218
          DNS Domain: bogusdomain

Link 2 (wlo1)
      Current Scopes: DNS LLMNR/IPv4 LLMNR/IPv6
       LLMNR setting: yes
MulticastDNS setting: no
      DNSSEC setting: no
    DNSSEC supported: no
         DNS Servers: 192.168.1.1
          DNS Domain: home

So theoretically, all we need to do is allow "." to be parsed as a valid domain here.