Undeliverable error 550 5.0.350

[Nate Long]

Anytime we send to a Yahoo or AOL email we get an Undeliverable message from Office365 with the error 550 5.0.350.
Reported error: 550 5.0.350 Remote server returned an error -> 553 you are trying to use me [server-30.tower-248.messagelab;s.com] as a relay, but I have not been configured to;let you [104.47.66.43, mail-mw2nam12lp2043.outbound.prot;ection.outlook.com] do this. Please visit;www.symanteccloud.com/troubleshooting for more details;about this error message and instructions to resolve;this issue. (#5.7.1)
DSN generated by: BN8PR15MB2978.namprd15.prod.outlook.com
Remote Server: server-30.tower-248.messagelabs.com

Here is the weird part, we do not use Messagelabs or Symantec products either on the endpoint or server/exchange.
We are using Office365 Exchange Online.
Why would it report Office365 is trying to use messagelabs as a relay?
All other email domains, custom or free, have no issues that we are able to tell.

I have used the Reputation tools from Symantec/Messagelabs as well as 3rd party and none report a bad reputation.
I have also confirmed that our SFP, DKIM and DMARC records are correct.
We are able to receive emails from Yahoo and AOL accounts.

This has been going on for months and I have made other posts with no help so I am trying again.

PLEASE, someone from Symantec/Messagelabs, help!!

[Bill Anderton]

I have the exact same issue in the exact same circumstances. It has been posted here and with Yahoo Support. I can't get a response and neither can Microsoft. We finally gave up. We are a regional law firm and the issue is blocking ALL of our one-on-one transactional email between our attorneys and their 4,000 clients with yahoo.com email addresses with active legal cases. These messages are NOT e-campaigns or mass mailings but one email to one client at a time. Been happening for weeks. Court documents, court settings and discovery being blocked. We have started advising all 4,000 clients to get a new email provider.