Outbound Exchange emails using MX records hitting O365 quarantine if recipient uses O365

I'm not sure I completely understand you scenario. You mention the outbound flow is via connector "to the recipient's domain", but then also mention that messages are caught but the O365 outbound spoof rule? Do you perhaps mean that the outbound connector is set to O365 (as in general it should be in such configuration: https://technet.microsoft.com/en-us/library/2e93fd60-a5ef-4e64-8e62-2b862b2d1033(v=exchg.150)#HowdoconnectorsinEOP)?

In general you should consider opening a support case, as this community is not a suitable platform for troubleshooting issues. You can find the support phone numbers here: https://technet.microsoft.com/en-us/library/jj723132(v=exchg.150).aspx