There is no barrier to entry other than excellence in search.
Your entire argument is based on a false assumption. It's like saying that there's no barrier to entry in the space mining business other than excellence in technology.
"Excellence in search" is not very easy, and given the Internets size requires a massive infrastructure by itself. In addition, you can have the best search engine in the world, as long as nobody knows about it, it's worthless. And since a large percentage of Internet users are only dimly aware that they're using a search engine when they type some words into the address bar, it's not as easy as you assume it to be.
All regulations will do in a situation like this is break the functioning market.
You missed the main part, I figure. Nobody is trying to break up the search market. Anti-trust is all about preventing a dominant player in one market from leveraging its dominance to become a dominant player in other markets where it would not prevail on merits alone.
The search market, for all this regulation, would be unchanged.
European regulations should be focusing on the edges of the market where Google is trying to manipulate things, such as forcing them to randomize product listing instead of always listing their own first.
Great idea!
Oh, wait...
That's exactly what they're thinking about.