Surprised they don't make their own Android phones
They are the only company that has all the pieces needed to completely replace Google's stuff like search, maps, app store, browser etc. The "MSAndroid" app store would be bare at first, but they have deep pockets and could provide incentives for developers who have Android apps on the Play Store to copy them to Microsoft's store.
Even if they didn't make any money off it, I'm sure they wouldn't mind taking all that user data from Google.
They could introduce some proprietary stuff that ties them into corporate Windows networks really well and not only take most of the corporate Android, but probably take a chunk of the corporate iPhone market away from Apple.