Comment by lorenzhs

Very good. See https://www.fastmail.com/help/receive/search.html for an overview of what it can do. It's also quite fast, I have a decade of email in my account (tens of thousands of messages) and a search through all of these messages takes only a second.