Exchange 2016 not able to receive external emails but Can Send externally

Hello,

I have an issue that I have been struggling with for the last few days.

We have exchange 2016 installed on windows server 2012 r2 physical box and we have an Edge Server installed on a windows server 2012 r2 physical box.

We are able to send and receive emails internally and we are able to send emails to other domains (Externally) but we cannot RECEIVE emails.

When I check the mail queue on the EDGE server I see the mails that were sent from outside our network either in Queue ready to be sent or with the following errors

SmartHostConnectorDelivery 451 4.4.0 DNS query Failed The error was DNS query failed with error ErrorRetry

DnsConnectorDelivery 451 4.4.0 Dns query Failed The Error Was: DNS query Failed with error InfoNoRecords

DnsConnectorDeliver LRT = 10/29/2017  ; LED = 441 4.4.1 Error encountered while communicating with primary target ip Address "etc"

Any advice?