Search has the benefit of all they data they have from the millions of other users who searched the same term and clicked certain results. It also has the backing of Pagerank. Your email is unique to you and doesn't have any of these advantages.

Regexp.

It's cool to hate on Google though I thought?

But seriously, all these hard core unix fans seem a little odd here. Gmail search has always been powerful, and is even more powerful now. It sounds like a case of user error if it isn't working for someone.

Not OP, but here's something I miss in Gmail search all the time-- ability to target a search at a particular directory and its sub-directories.

Suppose, for example, I have set up a subdir for conferences. That subdir contains a bunch of subdirectories for individual conferences. I know the e-mail I'm looking for is stored in there, because it relates to a conference publication I wrote. However, that subdir itself is "empty" as far as gmail search is concerned (because it's a "tag" rather than a true subdirectory).

The net effect of these hollow imitations of directories is I can either target the search to a specific tag, or I can search throughout my entire collection of messages. (Or, I suppose, I can tag every e-mail with every single sub-tag represented in the directory hierarchy I have mentally set up, just in case I might want to search for it someday.)

The gmail ideal, of course, is that I abandon the notion of directories altogether, and just let all my messages stew in the ocean of e-mail that one accumulates over the years. Supposedly their "powerful" search capabilities will help me find what I want. In my experience, though, under this approach most reasonable searches produce multiple pages of possible matches. This, of course, is hardly efficient.

It would also be nice if I could perform a search and then pull out that page of returned results into a separate screen/window for ongoing reference. Often when I'm searching for something, I'm looking broadly for resources or related conversations, rather than for a specific message.

Another place where I feel gmail search is brain-dead is its lack of regex capability (which @devdas has already mentioned).

The search I have the most trouble with is searching for things that match a label and are in my inbox. GMail will consistently miss messages. I don't know what it is about them, but I imagine it's some indexing bug. I can go to my inbox, click through the first several pages of messages, and see that a message is there, and has my label. I can go to my label, and find it there too. But a search for 'label:foo in:inbox' will come up empty.