Gmail does not support rich full-text search -- the indexer used is very limited. Among other things no synonyms, word stems, or subwords are indexed.
This is the biggest problem I have with gmail, and one of the principle reasons why I don't feel I'll be using it "permanently." My search queries very rarely find the emails that I'm looking for.
Seems like Google could easily treat it as a searching issue rather than a sorting issue, though. It would be easier than full text searching (which it already does).