I use the bridge and a real mail client with proton and the search is fine. You can even hook the bridge into tailscale, so it works across my devices with a real mail client also (e.g phones tablets etc).

The desktop client is rubbish, though, agreed.

Apple Mail the client or the web?

Apple Mail.app is the fastest search available. I use it with o365 specifically for search.

The app. With MS365 I get terrible search results. And worse, my work email has access to some shared accounts which I can’t access from Apple mail as 2FA will only work for the primary account.