Cannot send mail from Office 365 to Gmail - Delivery has failed

Check this article: https://technet.microsoft.com/library/dn458545(v=exchg.150).aspx You are blocked and the admin can unblock you.

 

Did you setup a SPF TXT record in your external DNS for your domain in Office 365? I guess you are sending emails via Exchange Online Protection (MX points to Office 365). If not, do this or send the request to your admin :)

I've seen two reasons for this:

1. Add the recipient address to your Allowed Domains in the Exchange Admin Center. I know that sounds wrong when you are the sender and the allowed domains are for inbound spam protection, but I've actually seen it work.

 

2. An Exchange Online outbound server has been blacklisted because someone was actually spamming from it. This happens rarely and they decommission it and re-route outbound mail through a different server, but you can get caught in the cross-fire. This should resolve itself over time. If it's taking too long, raise a support ticket.

 

Have you checked the system messages in your Admin Center for any known problems?