When Microsoft and Yahoo partnered in a search alliance just over 2 years ago, there were some naysayers, but there was also some optimism. The companies hoped that it would put them in a better position against Google.

Bing began powering Yahoo Search, Yahoo became the exclusive search advertising provider for Bing, and Microsoft’s adCenter began operating the self-service advertising division for both companies. Although the combined companies make up almost 30 percent of search market share, both Yahoo and Bing reported declining revenues in their recent earnings reports.

Is the Yahoo-Microsoft Search Alliance falling through? What do you think?

In a recent interview with Mark Ballard, the Senior Analyst at the Rimm-Kaufman Group, he told us that the partnership was backfiring on the companies. He said that it was hurting Yahoo more than Microsoft but that both companies were struggling.

Before the Alliance, Yahoo was much more liberal in how it matched ads to search queries. Ballard told us that it previously brought in around 60 percent of broad matched traffic and that it only brings in around 40 percent of broad matched traffic now that Bing is powering it.

“It really seems that Bing’s not doing a great job at figuring out which ads to show for certain queries… there are so many queries out there and we can only have so many keywords in our account that we rely upon the engines to do some smart matching,” he said.

Yahoo has definitely felt the heat from these results and, in its April earnings report, openly blamed Microsoft for its struggles. While Ballard believes some of the fault lies with Microsoft, he also pointed out that Yahoo should have considered this type of outcome before it agreed to an Alliance.

Microsoft has also been blasted for its failure to bring about significant improvements through the partnership. Reuters analyst Robert Cyran even suggested that Microsoft sell Bing and indicated that Facebook or Apple could do more with the search engine.

“Even though their revenues are growing, they’re still bleeding money on Bing,” said Ballard. “I think Microsoft probably is willing to take a loss on Bing because they see it as part of a larger strategy. Whether or not that larger strategy makes sense – I guess that’s for the C-level folks at Microsoft to decide.”

In a post he wrote on this topic, he pointed out that Bing could pull in more revenue by bringing on more search partners. This, however, would not be good for advertisers, since partner traffic is usually very poor quality.

Ballard believes that Bing needs to make technological changes and open their broad match to make it smarter. In addition, he told us that Bing needed to invest in ad innovations that are more appealing to users, which would deliver higher click-through-rates for advertisers. For example, Google has enhanced its ad formats in ways that go beyond the normal text ad.

He would also like to see Bing add more real estate for ads on Bing.com. If the search engine makes these adjustments, Ballard thinks both Yahoo and Bing would see a noticeable difference.

“We’re rooting for Bing and Yahoo,” he said. “They have the traffic, and we’d like to take advantage of it.”

Can Yahoo and Microsoft turn their Search Alliance around and on the right track?