Well, they already do (and have to) maintain separate indexes for each and every gmail account (or else how would you search on the metadata fields like To: and

Well, they already do (and have to) maintain separate indexes for each and every gmail account (or else how would you search on the metadata fields like To: and From: in your inbox at all?). Supposedly the issue is that they don't perform more computationally-expensive linguistic analysis during the indexing phase. If they tokenize each word but don't perform any stemming or lemmatization, for example, the result would be similar: only full-word non-substring matching. As others have pointed out, its probably a cost-benefit decision by Google to not spare grid cycles on full-fledged linguistic analysis for individual's email accounts. Google CAN do better at it, as is evidenced by their web search index.