I am using paid version of Proton Mail and search is working in thunderbird connected to their IMAP/SMTP bridge just alright. But web interface may suck, I did not use the web for a long time.