It's that second thing. They spend a lot and have a lot of talent behind keeping search up. Also it's an easier problem because it isn't transactional. They can fall back to generic search results if they can't load your custom data, and you'd probably never notice.

Google calendar sort of requires your personal data to function (just like gmail).

I'm guessing that Google search is easier to distribute over a larger set of machines, since the data it uses is static to a large degree and less bound to specific users.

Search also has the possibility of degrading nicely, unlike a calendar. You could store the top million sites in some backup service and drop down to string matching if you had to. Searching for “how to train a hunting dog”? Here’s the Wikipedia page for Dog. Best of luck.