When a third party spam filter (such as a Fortimail or Fortimail Cloud instance) is placed in front of Office 365 and Exchange Online Protection (EOP) is enabled you may experience the following rejections:

dsn=4.0.0, stat=Deferred: 451 4.7.500 Server busy. Please try again later from [x.x.x.x]. (AS780082)

This message isn’t very indicative of the problem and often Microsoft support isn’t very helpful in figuring it out.

A receive connector needs to be added in the O365 settings to allow incoming mail from the E-mail security appliance IP address:

Exchange Admin -> Mail Flow -> Connectors
Create a new connector
From: “Your organization’s email server”, To: “Office 365″
Click Next
Give the connector a name
Leave the 2 checkboxes checked
Click Next
Select “By verifying that the IP address of the sending server matches one of these IP addresses that belong to your organization”
Add the remote server’s IP address
Click Next
Click Save