The European Commission is seeking fresh concessions from Google on how it displays search results on web pages.
The long-running investigation aims to settle concerns that the search giant has abused its dominant position in the European search market.
Competition commissioner Joaquin Almunia revealed that he could also open a probe into Google's mobile operating system Android.
Google said it continued to work with the commission to resolve the matter.
The dispute has been running since 2010, after rivals, including British price-comparison site Foundem, complained that the way Google displayed results was anti-competitive.
In Europe Google has a 90% share of the search market.
In a deal hammered out in February, Google agreed to reserve space near the top of its European search pages for competitors, which would be open to rivals to bid for via an auction.
This auction could generate an extra income of up more than 300 million euros for Google, said rivals.
"Under the auction system Google would get another massive revenue stream. It's a bit like telling a robber than he can't rob any more but instead can set a toll on the High Street," said David Wood, a lawyer that represents iComp (Initiative for a Competitive Online Marketplace) of which Foundem and Microsoft are members.
"The real remedy is for Google to use the same algorithm for third-party sites that it applies to its own," he added.
He urged the European Commission to push this solution as part of its powers.
Writing on the Google Europe blog, executive chairman Eric Schmidt quoted Mr Almunia saying that imposing "strict equal treatment could mean returning to the old world of Google displaying only 10 undifferentiated search results".
"We're trying to get you direct answers to your queries because it's quicker and less hassle than the 10 blue links Google used to show," he said.
"Nor is it true that we are promoting our own products at the expense of the competition," he added.
Mr Almunia had previously indicated that he was happy with the changes but had changed his mind in the wake of "very, very negative" feedback from rivals such as Microsoft and Expedia, he said in an interview with Bloomberg TV.
"Some complainants have introduced new arguments, new data, new considerations. We now need to to analyse this and see if we can find solutions, Google can find solutions, to some of these concerns that we find justified," he told reporters.
This represents the third rejection of Google's solutions and experts think that it is now unlikely that an agreement will be reached during Mr Almunia's term in office, which finishes at the end of October.
If no agreement is reached, Google faces a heavy fine.