Update: Yahoo! and Google have indeed announced a partnership in the form of a non-exclusive deal allowing Yahoo! to run Google advertising alongside search results. The press release is here.

The clumsy $44 billion mating dance that began in February between Microsoft and Yahoo! officially came to an end today. Yahoo! and Microsoft each issued statements saying that talks had been concluded, though Microsoft left the door open for non-outright-acquisition partnerships. Meanwhile, multiple sources are reporting that Yahoo! and Google are set to announce some sort of search deal, perhaps as early as today. So what's next for both companies?

Yahoo!

Yahoo!'s stock sank 10% on the news that the Microsoft deal was definitely off the table. And the company reportedly lost three key employees today as well. Usama Fayyad, the Executive Vice President of Research, Technology Evangelist and key open source advocate Jeremy Zawodny, and EVP of the Network Division Jeff Weiner are all supposedly planning leave the company. Definitely not a good day for Yahoo!

Plan B prospects don't look great for the Sunnyvale, CA-based company. The brightest alternative is the prospect of a search outsourcing deal with Google. That deal, if it happens, could take any number of forms -- Google takes control of all Yahoo! search marketing, Google takes control of a portion of search marketing, Yahoo! open sources their search marketing allowing both Google and Microsoft to sell on their inventory, etc.

Given that Microsoft left the door open to an "alternative transaction," which we have speculated may be the acquisition of Yahoo!'s search business, it might be unlikely that a Google-Yahoo! deal would shut Microsoft out completely.

The dissolution of the Yahoo!-Microsoft acquisition talks also means more pressure is put on Yahoo!'s in house efforts to bolster their search business -- which slipped again last month -- such as SearchMonkey (our coverage) and Panama (our coverage). Last summer we wrote that the path to fixing Yahoo! started with a developer platform -- that's the direction they are headed with SearchMonkey. Without Microsoft, they have a lot riding on its success.

Microsoft

Microsoft has more options than Yahoo! Without Yahoo!, making a dent in Google's dominant search market share seems even more implausible, but the company can do other things to shake up their web business. We suggested a detail plan B in February that would have Microsoft "split up the search advertising atom" and basically open source their web marketing business. By breaking advertising up into inventory, placement, and parameters and allowing anyone to sell over this open model, we predicted that Microsoft could potentially make a huge impact on Google's web advertising dominance.

"Let Google be the search giant. Instead, focus on shaking up the advertising industry by pushing it toward a democratized structure, make it work for everyone, and weaken Google's business model," we wrote.

We've also suggested that Microsoft could put search on Facebook. "There are two ways people find information on the Internet: via search (which Google is great at), and via their friends (which Facebook is great at). The former we also know how to monetize. If Facebook can get good at search, it could stand to make a lot of money for whoever it partners with for that -- the logical choice being Microsoft," we wrote last month. Microsoft might even consider buying Facebook as an alternative to Yahoo!

Of course, not buying Yahoo! (or Facebook) would free up a ton of cash for Microsoft to do what it said it would last October: start investing heavily in small, web 2.0 start ups. Microsoft CEO Steve Ballmer said that the company would buy 20 companies per year ranging from $50 million to $1 billion for the next five years (likely they can acquire a lot of great technology for even less than that).

Our advice: invest heavily in mobile. If you can't beat Apple in the handset or software market, at least make a move to become the dominant content and advertising provider on the mobile web and beat Google to it.

What do you think are Microsoft and Yahoo!'s next moves? Let us know in the comments below.