This will serve as a quick reminder to myself that Debian behaves a little bit differently than Ubuntu when it comes to DNS resolving (in my defense, I have been working a lot on Ubuntu lately).
So, one of my Debian VMs had stopped resolving hostnames and I kept looking into /etc/network/interfaces to see if the correct DNS server was listed there. And it was. But that’s not the place to put DNS server information in Debian.
Then it hit me: if you are using Debian, put the DNS server you want to use inside /etc/resolv.conf. A quick look at the official Debian Network Configuration docs confirmed this.