Microsoft chief operating officer Kevin Turner, in an interview with The Times, stated, "[Yahoo has] a new CEO, and she’s formulating her business plans.  We’ve certainly made her aware and the Yahoo! board aware that if they are ever interested in an opportunity to partner with them on search, we’d like to sit down and at least have the conversation. It has to make economic sense to both parties."

Such comments represent the clearest sign yet to date that Microsoft is finding a post-reorganization Yahoo -- or at least certain parts of it -- rather desirable. 

For those who haven't followed Microsoft and Yahoo's rocky past relations, it all started in January 2008.  Yahoo, in bad financial shape and losing search market share to rival Google, was looking for a way to regain a competitive footing.  Microsoft approach Yahoo with what seemed a generous merger proposal. 

However, former Yahoo CEO Jerry Yang refused the deal, demanding more money.  Microsoft caved offering more money -- $47.5B USD in stock and cash -- but Mr. Yang and Yahoo's board still weren't satisfied and demanded yet more money.  At that point, the fire in Microsoft's heart died and the pair parted ways in a not-so-friendly manner, with each accusing the other of ruining the possibility for a relationship.

Fast forward a year and Yahoo has ousted Yang and installed a new CEO, Carol Bartz -- an outsider who is massively revamping Yahoo's management ranks.  Microsoft and Yahoo are in no better shape in the search market, and now have been further battered by a bad economy.  So in these trying times, with the major obstacle to a relationship (Mr. Yang) removed, Microsoft appears to be once again considering making a pass at Yahoo.

The one big holdup preventing such an entanglement is Microsoft's own projects it has been working on while Yahoo was away.  Microsoft has been working hard try to improve its search offerings and rise to be more than a bit player in the market.  It has been privately testing a new search engine codenamed kumo.com which may replace LiveSearch.

Any offer to Yahoo or potential partnership would have to reconcile how to incorporate these additions to Microsoft's search platform into a combined strategy, and how to make the large expenditure Microsoft's own search projects not for naught.

On the other hand, the greatest factor increasing the likelihood of a new offer is simply numbers.  Google, by the latest estimates holds approximately 63 percent of the search market.  Yahoo is hanging on at 21 percent, and Microsoft is holding out at 8.5 percent.  Together they might be able to make a legitimate challenger to Google, but separate, in their current form they seem unlike to pose a serious threat to Google virtual search monopoly.  With trends leaning in Google's favor, a turnaround seems unlikely without a partnership.

Microsoft believes one possible alternative is to create an iPhone-like Microsoft branded phone, and use it as a platform for Microsoft products, including bundling in its search offerings.  However, according to Mr. Turner, it has no current plans to make such a move.  He states, "Sure, we think about it, and, sure, it’s on the table.  But that’s not our direction today. For now we’ll work with our partners. After all, we’re going to sell 22 million copies of Window’s Mobile this year."

So with no "game changer" in sight for Yahoo or Microsoft -- other than Microsoft's new engine or Yahoo's reorganization -- its last January all over again.  Both companies are struggling to define themselves in the search market.  And they're once again finding each other increasingly attractive.