Enable the protocol logs for the receive connector on the Edge Servers and see if they are seeing these messages.
If so, it should tell you why its not accepting them:
IF you do not see them in the SMTP protocol logs, then open a ticket with 365 support. IF you are a 365 customer already, you can also look at the mail flow insights in EAC online:
https://learn.microsoft.com/en-us/exchange/monitoring/mail-flow-insights/mail-flow-insights