There are a lot of factors that can explain why they do not. The stackexchange says to avoid "Making statements based on opinion;" but I do not think that this is possible. There is most likely no one answer to this, and I would mark it a behavioral economic question instead of just micro economics. This answer assumes that your example gives each firm an additional profit.
1) Microeconomics assumes that each firm acts rationally; that is maximizes utility. Traditionally this means maximizing profit. This major assumption has been proved wrong again and again, and evidence suggest that the pure neo-classical model is not a sufficient indicator of firms actions.
2) While the end result of a contract will lead to a higher profit, the transaction cost between the firms may be high. Transaction Cost Theory basically adds friction to the invisible hand of neo-classical economics. Read the introduction, section 2.2-.3, and all of section 3.1. The external transaction cost between the two firms would be huge. Both companies are opportunistic, both firms have their own strategic intent, and assume both firms would not trust each other. What would have to result is an extremely ridged contract trying to encompass all possibilities, which can offset the additional profit both would obtain and lead to an extremely bureaucratic system that is not a characteristic of a successful tech company. For example, if I was using a Windows Cortana and searched via a joint venture with Google for a pc, would my search be directed to Microsoft's store or Google's store? A better example would Googles licensing rights. Would google be able to license it's product to other firms. If it was, it could charge a lower price else where via more favorable terms and undercut Microsoft all together (much like Microsoft did to IBM with DOS). If it couldn't, it would be depended to Microsoft, something the firm certainly does not need.
3) Google is dealing with anti-trust suits in Europe. For Google, teaming up with Microsoft to gain further market share would not go well in their efforts to prove they are not a monopoly, and it may bring anti-trust suit in the US. For Microsoft, given their history, I am positive they want to stay as far away from this as possible.
4) Potential may be the most over valued asset. While a search engine is valuable today, in the future having your own may be infinitely valuable. I am not a tech guy, but I can see the value in controlling what people find when they search certain key words. The short-term lose of potential profits as a result of an inferior search engine can be far out weighed by devolving one that meets industry standards. Add that with the fact that Microsoft's core business (OS) is not going to be undermined by a poor search engine, I can understand why they want to deploy their own.
As I said earlier, these are just possibilities, and a combination of factors leads them not to collaborate.