Dont think Apple would make a deal with any other engine. They basically used Microsoft to get a good deal with Google, but never had any intention to use Microsoft.

The thing is the deals are a revenue sharing deal - Google gives 1/3 of the revenue to Apple. With microsoft, the number could be 100% and would still not reach a significant number for Apple. Mozilla would jump at it, and I hope Google still invests in them as part of a grant or something while not getting anything in return.