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 :)