At the same time, Google may be frustrated enough with its attempts to get into the mobile market that it may be willing to negotiate an advertising revenue-sharing agreement that the operators can live with.

The stakes are high for Google. With over 2 billion mobile subscribers on the planet, mobile is the next frontier for online advertising. So far, none of the online search giants has established itself as the clear winner in mobile. "It's an open market. There is no dominant player," said Hazelton. Yahoo, AOL and Microsoft have also been aggressively rolling out services aimed at attracting mobile users who they can then advertise to.

Even if Google does manage to sign a deal with an operator, it still faces the technical challenge of trying to develop software that can work on any phone -- a problem that all mobile software developers face. One possibility could be using Java, which runs on most current phones, said Delaney. He thinks it would be a good idea for Google to partner with Sun, which last year bought SavaJe, a struggling mobile Java operating system developer. "If they're smart, they'd go to Sun and say, 'look, we both want to beat up on Microsoft,'" Delaney said. Google could build a user interface on top of the SavaJe OS and offer an open-development environment to developers, he said.

"Java would allow Google applications to run on a wide variety of devices," Hazelton agreed. "It could be a way to reach scale."

For now, however, the market will just have to keep guessing. Some news reports say that Google plans an announcement in a couple of weeks, but the search giant isn't commenting on the subject.