I have been having problems with one particular user in Office 365 who could not send or receive emails and he was always getting the error that the email was not delivered due to the below error.

Your message couldn't be delivered because you weren't recognized as a valid sender. The most common reason for this is that your email address is suspected of sending spam and it's no longer allowed to send messages outside of your organization. Contact your email admin for assistance.

Diagnostic information for administrators:
Generating server: --------------.eurprd02.prod.outlook.com
Remote Server returned '550 5.1.8 Access denied, bad outbound sender'

The problem is that the email was being blocked by Microsoft due that 5000 emails have been sent by the mailbox. The problem is not that your mailbox was hacked, but that the email header was spoofed by someone. To check that the mailbox is being blocked, open the Exchange Admin Center in your Office 365 portal, click on Protection and on Action Center.

You will see the user listed there with an unblock. Do not unblock the user for now.

In the Protection screen, click on dkim and highlight your external domain. Click on Enable. You will get an error message that CNAME records required are not found.

 

Open your domain DNS management portal on your hosting company and add the following CNAME entries

Host name: selector1._domainkey.<domain>
Points to : selector1-<domainGUID>._domainkey.<initialDomain>
TTL: 3600

Host name: selector2._domainkey.<domain>
Points to : selector2-<domainGUID>._domainkey.<initialDomain>
TTL: 3600

Once your DNS records have propagated, click on the Enable button on the dkim section.

Once enabled you can go under the Action Center and unblock the user. The process may take up to 2 hours to be cleared.

This will protect you from email message header spoofing. On another note to know immediately if a user has been blocked, you need to setup a notification as below.

Under the Exchange Admin Center open the Protection/ Outbound Spam section. Double click on default. Click on Outbound Spam preferences and tick send a notification when a sender is blocked as below and enter the admin email address. Click Save.