Please see Hub Transport fails when NIC is not set to register in DNS for an update to this article.
After installing Exchange 2016 CU8 on my Edge Transport server in a hybrid environment, I found that emails from on-prem users could not be delivered to EOP. They would queue with the following error:
LED=451 4.4.0 DNS query failed. The error was: DNS query failed with error ErrorRetry -> DnsQueryFailed: ErrorRetry
For troubleshooting I confirmed that name resolution works from the Edge Transport server using NSLOOKUP. I also was able to connect to the tenant SMTP namespace using Telnet on TCP 25 so I know that name resolution is working fine from the server.
Eventually I found that I had to configure the external DNS server in Set-TransportService and restart the transport service on the Edge Transport server to get emails to deliver.
Set-TransportService <edgetransportserver> -ExternalDNSServers 126.96.36.199 -InternalDNSServers <internal DNS server>
When I revert the change, emails start queuing again. I've reported this as a bug to Microsoft.