When using dnsmasq as a backend, Network Manager currently passes --strict-order.
This is a good way to get a similar behaviour to that of the libc's resolver where the DNS servers are being queried sequentially with a 2-3s timeout per server. However in the case where the first DNS server is down, this will delay all the DNS queries on the system.
Instead, I recommend this parameter be dropped which will fallback to the default dnsmasq mode to send the initial request to all servers and then continue with the first one that replies. This will increase the load on the upstream DNS servers quite a bit (though not as much as using --all-servers) but will ensure a proper fallback when some servers are down or very slow.
I think this added load is reasonable and shouldn't affect most DNS servers too much. For cases where it's a concern (heavily loaded corporate network for example), I'd suggest the user simply turns off the dnsmasq plugin in /etc/NetworkManager/NetworkManager.conf thereby reverting to the libc's behaviour of trying servers sequentially with a 3s timeout.