I use protonmail and the search is genuinely atrocious. Like the word can be in the title and it still won't find it.

I've used Protnmail before and had the same issue. I think enabling something like "full local indexing" or something made it better.