Below are the few solutions recommended by Microsoft these solutions, were taken from the Microsoft Doc site. For your issue any of the below solutions will help you:
Here are some steps for you to try:
Solution 1: The MX record for your domain might be missing or incorrect. Get more information about how MX records work at DNS basics.
Solution 2: Test your MX record and your organization’s ability to send mail by using the Outbound SMTP Email test in the Microsoft Remote Connectivity Analyzer.
Solution 3: The Sender Policy Framework (SPF) record for your domain might be incomplete, and might not include all email sources for your domain. For more information, see Set up SPF to help prevent spoofing.
Solution 4: Your domain might have expired due to non-payment. Verify with your domain registrar that your domain is active and not expired.
Solution 5: If the recipient is in your on-premises Exchange organization in a hybrid deployment, there might be a problem with your hybrid configuration. Give the information in the NDR to your on-premises Exchange administrators. They might need to rerun the Hybrid Configuration Wizard due to changes in their on-premises IP addresses or firewall rules.