You should check for SPF records as well. If they have SPF records (and Microsoft walks them through setting up those records), they would need one for every mail server sending on their behalf.
So it appears that in your case here their MX records pointed at their own MTA that then routes at least some of that email to Microsoft. If they are using SPF records to prevent others from spoofing their email addresses, and if they are allowing Microsoft to send on their behalf there would have to be SPF records with Microsoft's domains in them.
Still no sure thing but a little more checking that you can do.