Emails sent using 'mail.protection.outlook.com' are rejected as 'Access Denied', what can you do?

Question

If you find that emails are not arriving at their destination and find the following error in the Exim error_log, you may need to take the actions in the Answer Section.

Error found in Exim error_log:

SMTP error from remote mail server after RCPT TO:<example_user@domain.tld>: 550 5.4.1 Recipient address rejected: Access denied.

MX records for the receiving email server are 'mail.protection.outlook.com':

# host domain.tld
domain.tld mail is handled by 10 domain-tld.mail.protection.outlook.com. <-- here

# host domain-tld.mail.protection.outlook.com
domain-tld.mail.protection.outlook.com has address 104.47.6.36
domain-tld.mail.protection.outlook.com has address 104.47.4.36

Answer

There may be an issue at 'mail.protection.outlook.com' that needs attention. We found the below steps that may be useful in resolving the error.

Information found:

If external senders receive NDR 5.4.1 when they send mail to recipients in your domain, please try the steps below: 

1. Open the Office 365 portal at https://portal.office.com.
2. Click Domains and verify your domain appears in the list as Active.
3. Select the domain and click Troubleshoot. Follow the troubleshooting wizard steps.

If you maintain control of the DNS records for your Office 365 domain, you can also check the status of the domain in the Exchange admin center by performing these steps:

1. Open the Office 365 portal, click Admin, and select Exchange.
2. Click Mail flow > Accepted domains.
3. Verify that your domain is listed, and verify the Domain Type value for the domain. Typically, the Domain Type value should be Authoritative. However, if you have properly configured a shared domain, the value may be Internal Relay.

This information is from the following URL: https://answers.microsoft.com/en-us/msoffice/forum/all/mailprotectionoutlookcom-is-rejecting-my-mails/5a6bb9e0-062c-44e0-8a60-d79959bc003e