Had a user who started to get this message. “Your message couldn’t be delivered because you weren’t recognized as a valid sender”. Logged into their Office 365 Admin account and went to Protection >> Action Center. Saw the user there and clicked “unblock” them. It took a minute, and came back with the user still in the list. I tried to send an email at the user and got the same error. In the Admin panel >> Action Center the user was still listed. I clicked “unblock” again and this time the user wasn’t listed. I tried to send another email, and got the same error again. I see a alert on the Action Center page to go to the new “Restricted Users page“. This page didn’t show the user being blocked.

I looked at the error in the Non-Deliverable Report in the returned email. The error in the message is “550 5.1.8 Access denied, bad outbound sender“.

This page was a help to let me know it could take a few hours for the email to resume.

https://support.office.com/en-US/client/results?Shownav=true&lcid=1033&ns=O365ENTADMIN&version=15&omkt=en-US&ver=15

Let us know if this helped you…