The search collaboration that Ballmer referred to would presumably be similar to the search (as opposed to acquisition) deal previously offered to Yahoo — essentially to have Yahoo outsource search and SEM to Microsoft in exchange for guaranteed revenues over a several year period. Danny did a detailed post on the prior Microsoft search offer to Yahoo (compared with the now defunct Google deal).
That offer, as with the larger acquisition offer itself, was previously rejected by Yahoo as undervaluing the business. It was also rejected because it was seen by Yahoo as removing a strategic component of the company’s larger suite of advertising capabilities.
Circumstances have dramatically changed since Yahoo rejected Microsoft’s offer.
I have believed in a deal like this for a long time. I think it may well come to pass now. But I think the key is how to integrate the two offerings (Yahoo’s is generally seen as more battle tested and robust, and has a far longer history of monetization) and how to tie both companies’ massive traffic to the engine.