Where does sei.co.jp comes from? Why Microsoft would use that domain in the first place?

I'm willing to bet they were the first user to try and add example.com to their Outlook account, and MS then just assigned it to them without verifying they own the domain.

It's not really the domain but the registration in the MS Office Cloud. If you query who owns example.com mail you get that company.