what's your problem with mail search? works pretty well for me. it definitely can't beat gmail web search as I remember it from years ago:)

gmail is now such that I don't even understand the inbox.