After much fighting, I discovered the issue.
Take a look at your /etc/nssswitch.conf
In my case, it had these lines:
# Use /etc/resolv.conf first, then fall back to systemd-resolved
hosts: files dns resolve myhostname mymachines
# Use systemd-resolved first, then fall back to /etc/resolv.conf
hosts: files resolve dns myhostname mymachines
# Don't use /etc/resolv.conf at all
hosts: files resolve myhostname mymachines
I changed it to this in order to get things working:
# Use /etc/resolv.conf first, then fall back to systemd-resolved
# hosts: files dns resolve myhostname mymachines
# Use systemd-resolved first, then fall back to /etc/resolv.conf
hosts: files resolve dns myhostname mymachines
# Don't use /etc/resolv.conf at all
# hosts: files resolve myhostname mymachines
Not even a restart required!
$ curl google.com
<HTML><HEAD><meta http-equiv="content-type" content="text/html;charset=utf-8">
<TITLE>301 Moved</TITLE></HEAD><BODY>
<H1>301 Moved</H1>
The document has moved
<A HREF="http://www.google.com/">here</A>.
</BODY></HTML>
$ nslookup google.com
Server: 8.8.8.8
Address: 8.8.8.8#53
Non-authoritative answer:
Name: google.com
Address: 172.217.16.238
Name: google.com
Address: 2a00:1450:4009:821::200e
What a painful episode. Good luck!