(FastMail dev here) What problems do you find with the search? We have pretty comprehensive support for more or less everything Gmail search offers and more (https://www.fastmail.com/help/receive/search.html), but if we're falling short for your use case we'd love to know how, to help guide improvements for the future.