Now that a Yahoo acquisition is off the table, Microsoft is moving quickly to "fix" its online branding problem, an executive said Tuesday.

Microsoft has been criticized for the introduction of the Live brand, particularly because it didn't fully replace the MSN brand. That has created some confusion in the market, because some services from Microsoft, like Hotmail and Messenger, have both brands and it's difficult to determine if there is a difference between the differently branded services.

Now that Microsoft has pulled its acquisition bid for Yahoo, it plans to focus on solving its branding problem, said Kevin Johnson, president of Microsoft's platform and services division, speaking in Seattle on Tuesday at the Search Marketing Expo conference.

"When we made the bid for Yahoo, the full combination of those companies would have created a whole different set of brand opportunities for our marketing teams to solve," he said. "Since we've moved forward in not pursing a full combination at this time, our marketing teams are liberated to go solve that brand problem."

He suggested that his marketing executives essentially have free rein in deciding what to do. "Fix means fix," he said. The marketers may decide to build a new brand, and spend money to do so, and he'll support that decision, he said.

While a Yahoo acquisition is off the table, the companies do continue to discuss other alternatives, he said, despite very little comment from either company since acknowledging that talks about a more limited deal were happening. "We'll see where that dialogue leads, but there's nothing new to report," Johnson said.

Johnson also reiterated some of the themes that Microsoft executives have been talking about since the company pulled the Yahoo bid. "When you have a competitor that is entrenched, you have to focus on disruptive ways to change the paradigm," he said, referring to Google. Those changes could be in the form of user experience, the business model or the way consumers connect to the service, he said.

Microsoft has begun executing on this vision already, he said. The company's recently introduced Cashback service gives online shoppers money when they buy products from advertisers in Live Search. That's an effort to change the business model and the user experience.

In addition, on Monday Microsoft announced a deal with Hewlett-Packard that will result in a Live Search toolbar on HP PCs sold in North America starting next year. That deal will help distribution of the service, Johnson said.