I think it's quixotic to compete with Google/Bing on the index size. A good bet would be to try to compete on search flexibility i.e. allowing for various ways of slicing/dicing results, recombinance etc. IMHO Search needs a paradigm shift from the 10 blue links to a knowledge engine (a la Wolfram alpha).
The vast majority of searches can be satisfied by some of the open source indexes. For the "long tail", there is always Google.