Online freedom advocates fear that Google is changing allegiance in the battle to stop Internet service providers from giving preferential treatment to those that pay.
The concerns surfaced amid reports in the New York Times and elsewhere that as early as Friday Google and Verizon could announce that online traffic such as video from YouTube would move faster, for a fee.
Such an arrangement would be a major blow to the campaign for "net neutrality" in which no content is given priority treatment online.
"The New York Times is quite simply wrong," Google spokeswoman Mistique Cano said in an email response to an AFP inquiry.
"We have not had any conversations with Verizon about paying for carriage of Google or YouTube traffic. We remain as committed as we always have been to an open Internet."
Google has long championed net neutrality, which has also been a priority for the Federal Communications Commission (FCC).
Talks with Verizon to establish tiered pricing for Internet data traffic would be seen as a reversal of position.
Verizon issued a softer denial, hinting that it was collaborating with Google but that their intentions were honorable.
"Our goal is an Internet policy framework that ensures openness and accountability, and incorporates specific FCC authority while maintaining investment and innovation," Verizon spokesman David Fish said in a blog post.
"To suggest this is a business arrangement between our companies is entirely incorrect."
Internet and telecom giants had been meeting with FCC officials regarding a net neutrality strategy.
The FCC on Thursday called off further meetings, saying that while productive, the talks have "not generated a robust framework to preserve the openness and freedom of the Internet."
"It is a huge issue, because at the end of the day there is only so much spectrum out there and it is only going to carry so much," said Internet analyst Michael Gartenberg, a partner at Altimeter Group.
"It is a fuzzy situation, but it underscores the tensions that are going on."
A proposal put forward by FCC chairman Julius Genachowski calls for broadband Internet service to be reclassified as a telecommunications service.
That would force Internet service providers (ISPs) to adhere to the same strict fairness rules for consumer access as apply to telephone companies.
"Any outcome, any deal that doesn't preserve the freedom and openness of the Internet for consumers and entrepreneurs will be unacceptable," Genachowski said during a press conference on Thursday.
Internet companies such as Google need to be able to deliver video and other data quickly, meaning that to survive they might need to cut deals with ISPs, according to analyst Rob Enderle of Enderle Group in Silicon Valley.
The United States is short on bandwidth needed for its Internet-heavy lifestyle and government is not solving the situation, he argued.
"When government fails to govern, citizens, companies in this case, have to step up and fix the problem," Enderle said. "It's a mess. Congress is the one that really needs to fix it."
In April, a US appeals court dealt a major setback to the FCC's efforts to force ISPs to treat all Web traffic equally.
The court ruled in favor of broadband provider Comcast Corp. in a case seen as a test of the FCC's authority to enforce net neutrality.
The court decided that the FCC had not been granted the legal authority by Congress to regulate the network management practices of ISPs.
Nonprofit group Consumer Watchdog portrayed any compromise by Google on net neutrality as a betrayal.
"Apparently Google redefines principles to suit the business need of the moment," said John Simpson, a consumer advocate with the group.
"What Google and Verizon are trying to do is carve up the Internet behind closed doors for their own benefit."
The Eastern chapter of the Writers Guild of America also came out against the purported collaboration between Google and Verizon, saying that paying for online speed would cripple the ability of small players to compete.
A deal between Google and Verizon to pay for faster Internet routing would become a standard that other telecom giants would eagerly embrace, critics predicted.