Google and Yahoo had hoped to have it all up and running by now. As you may recall, the two Internet giants announced an alliance last June in which Google would supply Yahoo with search ads to supplement Yahoo’s own. Google would get a big new customer for its ad-delivery service, while Yahoo would get a new source of revenue – and best of all, they’d keep Microsoft from swallowing Yahoo.

Then Washington got in the way. Due to pushback from antitrust regulators, in early October, Google (GOOG) and Yahoo (YHOO) put off the launch to give the Justice Department more time to chew on it. In September, Justice reportedly hired veteran antitrust litigator (and former Walt Disney vice chairman) Sandy Litvack to help review the deal, and soon thereafter Canadian authorities hired an outside lawyer too. The European Union is also taking a hard look.

What’s the hang-up? Well, there are three basic concerns about just what this alliance really amounts to. First, if it had been a merger between Google, with 70% share in the paid-search market, and Yahoo, with the next 20%, it would clearly violate antitrust laws by creating a monopoly. (Paid-search ads are the ones that show up near the top of a search-result screen or off to the side, under the rubric “sponsored links.”) Second, if Google were paying Yahoo to exit the paid-search arena, that would be an illegal agreement between competitors to allocate markets. Third, if Google and Yahoo were agreeing to set a price floor for the two companies’ paid-search offerings, that would be illegal price-fixing.

The actual deal being proposed looks something like a slow-motion version of the first two scenarios, and it might constitute an immediate realization of the third.

Google and Yahoo have tried to placate skeptics with a raft of reassurances: They’re not merging; Yahoo will continue to compete in paid searches; ad prices will continue to be set by auction, with each company’s auctions operating independently; Yahoo will only run Google ads to the extent it chooses; and Yahoo is still free to display ads from other paid-search providers, including third-place Microsoft (MSFT).

Not everyone is convinced, though – notably advertisers. The Association of National Advertisers (ANA), the Association of Canadian Advertisers, and the World Federation of Advertisers have all written regulators to voice opposition. In the letter from the ANA – a 375-company association with a board that includes members from Wal-Mart, Sears, and McDonald’s – CEO Bob Liodice writes that his group “is aware of only one advertiser/marketer that does not object to the Google-Yahoo collaboration.” (Liodice wouldn’t identify the exception.)

MICROSOFT GETS SUSPICIOUS

One big problem for Yahoo may be an astounding comment allegedly made by its own CEO, Jerry Yang, during negotiations with Microsoft in a San Jose airplane hangar on June 8, just three days before the Google-Yahoo pact was unveiled. (Google offered Yahoo the ad deal in an apparent effort to keep it out of the hands of Microsoft, which had offered to buy Yahoo at a 75% stock premium.)

According to testimony that Microsoft general counsel Brad Smith later gave to the Senate Judiciary Committee, Yang peered across a conference table and said, “Look, the search market today is basically a bipolar market…. On one pole, there’s Google, and on the other pole, there are Yahoo and Microsoft…. If we do this deal with Google, Yahoo will become part of Google’s pole.” Smith and his Microsoft colleagues were dumbstruck. Smith testified that during a break a few minutes after Yang’s comment, Microsoft CEO Steve Ballmer cracked, “[Yang] said there’s only going to be one pole in the market. I guess that would be a ‘mono-pole,’ wouldn’t it?”

When stunned Senators demanded that Yahoo general counsel Michael Callahan, who had also been present at the June 8 meeting, give his account of what Yang had said, Callahan repeatedly refused until, when pressed, he finally said, “I don’t recall that comment.”

Even putting aside the disputed remark, there are plenty of reasons to be skeptical about those reassurances from Yahoo and Google. For example, consider Yahoo’s claim that the deal will enable it to compete harder in the search business. The company has told shareholders that it hopes to make $800 million a year from its pact with Google – money that, as Yahoo president Sue Decker has written on a company blog, will be plowed back into R&D “to help us become a stronger competitor in all aspects of online advertising,” including paid searches. Yahoo has an incentive to do so, the company says, because it keeps all the revenue from its own ads but only a portion from Google’s.

Hmm. What portion will Yahoo keep when it uses a Google ad? That’s not public. But according to a lawyer close to the Google-Yahoo camp, Google’s ad deals with web publishers large and small-from the New York Times website to GPSworld.com -typically leave the publisher with “the lion’s share” of the revenue. Accordingly, when Yahoo runs an ad delivered by Google, we’re probably not talking about a 50-50 split; it’s more like 90-10, with 90% staying with Yahoo. So if Yahoo can make 90% of what Google’s superior mousetrap currently yields while incurring no research expenditures, how great is its incentive to keep dumping hundreds of millions into R&D for its own clunkier mousetrap? Plus, if Google really thought the deal would help Yahoo build a more competitive paid-search program, would Google be doing the deal? Concern about the deal’s sapping Yahoo’s long-term incentive to compete is presumably a key factor spurring EU regulators to nose around, notwithstanding its ostensible geographical limitation to the U.S. and Canada.

THE PRICE PROBLEM

Then there’s the price-fixing issue. Nobody’s price fixing, Google and Yahoo insist, because ad prices will continue to be set by separate auctions. That’s true. But part of the idea with this alliance is to replace some Yahoo ads on Yahoo search screens with Google ads, when the Google ads will fetch more revenue. Here is an oversimplified hypothetical example: Suppose you’re an auto parts dealer trying to drum up some business with search ads. You bid for the query “spark plugs Dallas Texas” on both the Yahoo auction and the Google auction-and learn that the going rates on Yahoo and Google, respectively, are $0.80 per click and $1.20 per click. Google reaches more users – hence the higher bids – but you decide to go for the $0.80 ad on Yahoo.

Guess what? You’ll need to pay the $1.20 anyway. Why? Remember that with the Google alliance, Yahoo now has the choice of going with ads delivered through its own system or through Google’s. Yahoo, of course, is going to run the ad that makes the most money – the ad from Google. In fact, Yahoo would never run its own ads if they were priced more cheaply than an available, comparable Google ad. In that sense the Google ad prices, though set by auction, would effectively set a floor for the prices of comparable ads displayed on Yahoo. Price floors constitute illegal price fixing.

Yahoo and Google respond that Yahoo won’t have the real-time pricing information about Google’s ads it would need to make instantaneous price comparisons to Yahoo ads. Still, Yahoo obviously thinks it has some way to compare the relative prices of Google and Yahoo ads – how else will it know when to replace a Yahoo ad with a Google ad?

Which is not to say that the search giants’ formidable teams of lawyers won’t eventually win Justice’s blessing for the deal. Clearly, though, those lawyers still have some serious work to do.

[CLARIFICATION: A spokesperson for Yahoo says that the way I’ve described the “$800 million” annual revenue figure above is inaccurate. To be clear, what Yahoo said in its announcement and SEC filing was this: “Yahoo! believes that this agreement will enable the Company to better monetize Yahoo!’s search inventory in the United States and Canada. At current monetization rates, this is an approximately $800 million annual revenue opportunity. In the first 12 months following implementation, Yahoo! expects the agreement to generate an estimated $250 million to $450 million in incremental operating cash flow.” What Yahoo president Sue Decker said during the June 12 teleconference call was this: “In the first 12 months following implementation, we expect this agreement to generate $250 million to $450 million in incremental operating cash flow. Over the longer term, Yahoo! believes this agreement enables the company to better monetize Yahoo!’s search inventory. At the current monetization rate, we believe there is an approximate $800 million in annual revenue opportunity in the U.S. and Canada on those queries where monetization upside exists. This revenue opportunity could be achieved either from this arrangement with Google, which includes both search and nonsearch elements, or from other enhancements to our search capability, or a combination of them.” — RHP]