you should also consider that Google is/was the best search engine around so it makes sense as a default, sure they pay to be the default and most people never change defaults. But if you are making a phone you might just really actually care about people having a good experience with your phone.
(and its not like Microsoft couldn't pay them either anyway)