So I discovered this today, and figured I'd pass it along in case anyone else is running into the same problem.

Before fixing it this morning, I'd connect to my (work) VPN and would be unable to resolve internal hostnames on the remote network. Turns out there was a regression in network-manager, and an older version was re-pinned to bionic-updates. If you've having this problem, "update" network-manager to version 1.10.6-2ubuntu1.1 (apt install --reinstall network-manager=###)