I'm on 17.04 too and suffering from this issue for a while.

As I understand this issue, the problem may actually very well be in Network-Manager rather than in systemd-resolved, but the problem is indeed very visible with resolved.

Here's how I experience the problem (the root of my problems are a split DNS setup, just like most other people following this ticket).

This is the state of my resolved...

With no VPN connected (wireless and wifi only):

Link 7 (vpn0)
      Current Scopes: none
       LLMNR setting: yes
MulticastDNS setting: no
      DNSSEC setting: no
    DNSSEC supported: no

Link 3 (wlp4s0)
      Current Scopes: DNS LLMNR/IPv4 LLMNR/IPv6
       LLMNR setting: yes
MulticastDNS setting: no
      DNSSEC setting: no
    DNSSEC supported: no
         DNS Servers: 192.168.8.1
          DNS Domain: int.example.com

Link 2 (enp0s31f6)
      Current Scopes: DNS LLMNR/IPv4 LLMNR/IPv6
       LLMNR setting: yes
MulticastDNS setting: no
      DNSSEC setting: no
    DNSSEC supported: no
         DNS Servers: 192.168.8.1
          DNS Domain: int.example.com

With VPN connected:

Link 7 (vpn0)
      Current Scopes: DNS
       LLMNR setting: yes
MulticastDNS setting: no
      DNSSEC setting: no
    DNSSEC supported: no
         DNS Servers: 192.168.180.48
                      192.168.180.49
          DNS Domain: example.lan

Link 3 (wlp4s0)
      Current Scopes: DNS LLMNR/IPv4 LLMNR/IPv6
       LLMNR setting: yes
MulticastDNS setting: no
      DNSSEC setting: no
    DNSSEC supported: no
         DNS Servers: 192.168.8.1
          DNS Domain: int.example.com

Link 2 (enp0s31f6)
      Current Scopes: DNS LLMNR/IPv4 LLMNR/IPv6
       LLMNR setting: yes
MulticastDNS setting: no
      DNSSEC setting: no
    DNSSEC supported: no
         DNS Servers: 192.168.8.1
          DNS Domain: int.example.com


Now, I have one split DNS entry, testserver.example.net. On a public DNS, it will resolve to a public IP - On the example.lan DNS servers, it will resolve to a private IP.

Doing the following a couple of times is bound to sometimes return the private IP and sometimes the public IP:

systemd-resolve --flush-caches && ping -c1 testserver.example.net

So for things to work in this particular example, I'd need the 192.168.8.1 DNS to either be disabled completely or only used for int.example.com. 192.168.180.48 and 49 as provided by the VPN would somehow need to be the default/active nameserver. Note that for my VPN connection in Network Manager, I've *not* enabled the "use this connection only for resources on its own network".

In an attempt to work around this problem, I decided to configure network-manager for dnsmasq, which worked fine back in the 16.04 days. Basically the setup worked, but Network-Manager only added the VPN DNS servers for the VPN provided search domain example.lan. Needless to say this works even worse than the resolved solution, because now I get the wrong answer for testserver.example.net every time. It does seem to indicates that perhaps there's something fishy about how network-manager passes DNS servers to resolved. I have not found a way to force network-manager to completely replace the configured DNS servers for a VPN connection, but that might provide a usable workaround.

Hopefully this can shed some light on things?