MSN vice president Yusuf Mehdi told investors Tuesday that Microsoft is working overtime to increase its share of Web searches in the face of strong competition by Yahoo! and Google. With only 9.5 percent of search queries, Microsoft has long a road ahead as it endeavors to chip away at Google's 60 percent hold on the search market, Mehdi said.

The conference for investors came one day after MSN's announcement that it was joining the desktop search arena with its MSN Toolbar Suite Beta.

"I think what we've done in the past 20 months is, quite humbly - amazing," Mehdi said, referring to the less than two year turnaround for the desktop search program from concept to beta release. The charge to do something with MSN Search came directly from the top: Microsoft Chairman Bill Gates.

"We'll never be as cool as them. Every conference you go to, there they are dressed in black, and no one is cooler!" Mehdi told a Newsweek reporter last summer regarding the bigwigs at Google. But behind the scenes, the gears were working overtime at Microsoft.

The main problem with MSN Search, insiders say, is the fact that while it may garner over one-third of the unique users that visit search engines, it only accounts for one in ten search queries. "That is what happens when you let a competitor do your search," a source within Microsoft told BetaNews, referring to the fact MSN has let Google handle some of its searches.

The new MSN Search engine, now in beta, fixes that; all search results are handled solely by Microsoft. With a host of new features such as "search near me," which turns generic queries like "weather" into powerful search terms that actually give the user immediate results, Microsoft means business.

At the beginning, however, not everybody was on board believing that Microsoft could really make a dent in Google's near-complete dominance of the search market. Even the normally optimistic Mehdi lacked faith. "I didn't think we could be a strong player in the market," he told investors.

But, emboldened with the fact that Yahoo! removing Google results from its listings resulted in a 20 percent decrease in market share for Google in less than a year, Microsoft began to think it just might happen. Now, the company is singing a different tune when it comes to the subject of search. "We're in a very good position to grow our share," Mehdi told investors.

According to Microsoft, the release of the MSN Toolbar Suite and new search was only the first phase of a three-step program to get the company to where it wants to go. Right now, says MSN's Mehdi, Microsoft is focused on making the searching experience enjoyable for its own customers.

The second phase, "in one to two years," will make search more enjoyable to everyone, whether they are a customer of Microsoft or not. Then, in the final stage, the company will release an API for developers to plug into and build applications based on its search technology.

It may sound like am ambitious plan, but Microsoft executives have renewed confidence in their efforts. When asked what he now thought of MSN's search prospects, Mehdi responded, "I am increasingly optimistic."

Nate Mook contributed to this report.