As speculation ever swirls about Yahoo and Microsoft joining forces to give Google a better run for its money in search, one party in the on-and-off  negotiations has been notably evasive this week. “If we ever have a deal with Microsoft, it will be announced publicly and until we do, we have nothing to say,” declared Yahoo CEO Carol Bartz at the company’s shareholders meeting yesterday in Santa Clara, California.

A world away in France, one day before, I did an onstage interview with Steve Ballmer, Microsoft’s CEO, at the Cannes Lions International Advertising Festival, And of course I asked him about the likelihood of a deal with Yahoo. Some industry watchers have speculated that the early success of Bing, Microsoft’s new search venture that debuted June 1 (and in less than a month boosted Microsoft’s share of U.S. search results pages to 12% from 9%, according to comScore) makes a Yahoo deal less essential–for Microsoft, at least. Here, in this excerpt from our Wednesday conversation in Cannes, Ballmer suggests that’s not necessarily so…

Sellers: For every share point that you gain in search thanks to Bing, by what percent does that decrease the need to do a deal with Yahoo?

Ballmer: Have you ever heard of a more back-handed way of asking the question than that?  Oh my God… (He waits for audience laughter to die down.) OK, I’m going to try this one time. First of all, we have no interest in acquiring Yahoo.  Can I…? I’ve said that 88 times. I’ll say it the 89th just to make sure it’s clear.

I have said, and I will continue to say, we remain open to a partnership with Yahoo. I think the thing that advertisers. probably more than anything else, appreciate is: When you have two players that are fairly low-share, sitting in an advertiser’s shoes, you have to decide how many of the “search engines” do you bid on and how many key words do you bid on per platform? More people, more advertisers bid on more key words on Google than on Yahoo or Microsoft–even more dramatically outside the U.S. than in.

Forget the economic side to that story, it also affects the product.  The more relevant ads the search engine can serve up, the more relevant the whole page looks. When your average consumer looks at the search page, they don’t just say, “I’m going to look at the algorithmic results.”  They look at the whole page, including the ads.

So, I will tell you, I have a friend who rents apartments–mostly to American tourists. She rents apartments in Paris. If I wasn’t her friend, she would not submit bids. In the old days of 8% share–this goes back a year–she wouldn’t probably bid on our system. She’d only bid on the market leaders. So now somebody types “apartments in Paris for rent. And they’re going to get the relevant ad on the market leader. And they may not get the relevant ad on Yahoo or on Microsoft.

So a partnership makes sense, not because of technology just. Or business just. It makes sense because I think we can provide a better product through scale to our users based upon the kinds of interactions we have with advertisers. I want every bid on every key word that every advertiser in every part of the world would put on Google, I want on our system. As much not just for the revenue, but as much for the value in terms of the relevance of our offering as anything else.

So, am I open to a partnership with Yahoo? We remain open to a partnership with Yahoo.

Sellers: So what’s the likelihood that there will be a partnership in the next year?

Ballmer: Who knows?  Who knows?  I can…

Sellers: Carol Bartz wants “boatloads of money.” Don’t you have, like, almost $30 billion of money in cash?

Ballmer: We’ve got shareholders who want to make sure we take good care of it.

— Thanks to Joshua Glasser and Jessica Shambora for additional reporting.

[cnnmoney-video vid=/video/technology/2009/06/26/f_tt_microsoft_yahoo.fortune/]