(I work for Fastmail). Our search is comparable and in some ways more powerful than Gmail's search. If you're having problems, please create a support ticket (or just email [email protected]) and we'd love to look into that for you. Thanks!