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

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?