Answer by Adam D'Angelo:
Someone from Gmail could probably answer this better, but here are some factors that make mail search harder in some ways:
- The total contents of the web is actually smaller than the sum of the sizes of the contents of everyone's gmail. This means it could take more servers to hold all the indexes for mail search than for web search. 
- When you search the web, for the most part, you're getting the same results for your query as anyone else would get for that query. This means caching works well for web search. Most search engines have a small "hot index" with the most popular content that can handle the majority of queries which is replicated out to lots of local datacenters, giving low average response time even if the worst case is slow.
- Gmail search results are sorted by time and need to be perfect matches, whereas web search results are sorted by relevance and approximations can be made to cut corners.