Interesting that each of these have multiple mx records and both have issues. I don't think this is your problem, I think its on them to fix.
In both examples they have mx records that are not valid any longer.
basmalta-com.mail.eo.outlook.com is wrong and not supported anymore, it should be set to the correct mx record for their domain in 365. ( the eo. part)
in the second example, the mx record with a preference of 10 is invalid. Its possible your server is attempting to send to that secondary MX record.
can you contact them and let them know? :)
otherwise, this is not on you to fix.. you can point them to: https://learn.microsoft.com/en-us/exchange/troubleshoot/email-delivery/wrong-office-365-region-exo