No; these reasons show why the are is ripe for anyone to do it. The only fallacy in Paul Graham's comment (or in possible interpretations of it) is that Google has a weak spot there so it's an opportunity for somebody else to beat Google. Trust me, we have a ton of resources dedicated to improvements in search and we have lots of cool things coming down the pipe, although maybe not in the velocity that one could dream (e.g. something like intelligent research for scientific papers is firmly in the sci-fi realm today, at least for fully-automated computing).

BTW, Paul's article has a big #fail when he mentions code search as a possible idea; dude, we do have that and it's amazing (but unfortunately we recently shut it down; not sure if this will eventually resurface as part of some other product).

All that said, of course some company can always make an effort dedicated to a specialized niche that we are overlooking and beat Google Search in that niche; an excellent example of that is Wolfram Alpha. Still, not a big deal; to really "beat Google" you need a new general-purpose, full-Web search engine that beats Google's. Not impossible either, but the barrier to entry is simply colossal and it amazes me that people don't realize that and dream that it just takes some cool new idea or clever new algorithm to do that--we are not anymore in 1998, when Google, still working off a garage, started to beat the current top engines like Yahoo! and AltaVista.