Yes, search is hard. Look how most websites that build a search for their own site still do a worse job than Google's site search. And its not like people haven't tried to take on Google. Google always faces the threat of companies succeeding in smaller areas of search, but so far it's dealt with those pretty well too. The other threat it faces is a (big) company developing an alternative approach, e.g IBM Watson.
