Currently Online 
An alliance with Nintendo could make some sense IMO, it sounds to me like some factions within MS are simply tired of running the game business, Nintendo could step in and run it easily and obviously they are not going to leave the game business as it's their only business. They are right across the street from each other in Redmond/Seattle for one.
Nintendo could take over the Halo franchise and 343 Industries and get Rare back together and let most of the people at the XBox division to probably continue working right from Redmond/Washington.
Perhaps MS could score something out the deal too, like Windows mobile and Skype on future portable Nintendo devices -- that could be quite a coup for both sides.
I don't think MS would willingly sell to a Android competitor like Google or Samsung. Nintendo is of no threat to MS' wider business goals as they have no aspirations of making a computer/smartphone OS.
