I would also mention DNS over TLS as a possible problem. Try to do a trace route anc check for rules that block traffic to the DNS Server/s.
Another thing that might be required at some point is DNSSEC, give 9.9.9.9 a chance. (Cloudflare is of course a good one, too, but not in terms of security and threat defending)