> I am leaning towards search being a natural monopoly due to the huge resources required to build an index/algorithms/etc

A bigger issue are the network effects - no website can afford to block Google; not so much for your startup search engine.