Nokia, WIndows and Android
This case is about bundling and abuse of market position. Google Search is not a requirement for Google's Calendar or App Store to work, but licensees are forbidden from replacing it (you can put something else on the phone as an app, but you can't replace it). In the same way, Internet Explorer was not essential to running the Windows OS, and yet licensees were forbidden from replacing it. Microsoft's sins don't become virtues just because it's Google committing them.
Nice to see the everlasting "Nokia should have used Android" comment is still doing the rounds. Actually, Nokia's negotiations with Google back in 2010 are illuminating for this case, even though they didn't involve search.
Contrary to some conspiracy theorists, Nokia did negotiate with Google before dumping Symbian. During these negotiations, Google made it very clear that Nokia could adopt Android (or more correctly, join the Open Handset Alliance), but what Nokia could not do was use their own mapping and navigation service in place of Google's. (Same for Nokia Music, which is at similar level as Google's music store, and had cost a lot of money to set up, and was generating good revenues)
They could of course just port Android to their hardware without OHA membership, but if they wanted to go their own way like this, they would be barred from access to Gmail, Google Calendar and what is now the Play Store: they'd have ended up with all the downsides of Android and none of the benefits, plus the extra costs of duplicating Google's services (as Ovi showed, this was exactly what they wanted to avoid).
As a "concession", Google offered to buy Nokia's mapping and location division from them. That would not only have been a bad deal for Nokia, but would have sucked for consumers, as Navteq/Nokia is Google's largest competitor in mapping software.
In contrast, when Nokia went to Microsoft (already a Navteq customer, incidentally), MS were prepared to concede the mapping, allow Nokia to add their own services to the OS package, and MS offered discounted licences and marketing support.
That's why Nokia did not, and will not, make an Android phone. Google's terms gave Nokia very little value.
You can look at their choice of Microsoft as bribery, or even betrayal if you're the sort of person who emotionally invests in legal constructs, but it's nothing of the sort. Nokia's purpose is to do what is best for Nokia's shareholders. Just as Google's only purpose is to do what is best for Google's shareholders, and Microsoft's purpose is to do what is best for Microsoft's shareholders. In this case, Microsoft and Nokia were able to create an arrangement that benefited both; Google's offer benefited only Google.