I actually heard that it's quite costly to index emails for gmail (not from a gmail source, just random web chatter). It makese sense. Most emails are not important, they are just huge amounts of random chatter. I'd imagine indexing emails (full-text) properly would require some effort. The gmail team is probably on a budget :)

But then again, if they can index the web. Why not email.