I’m using native mail app of iOS/macos and search bar works for me. However, iOS has a persistent issue of not fetching new mails, even from iCloud, which has support for push updates. I inadvertently build a habit of opening mail app and refreshing.
I find it often won't even refresh when you click the little envelope "get mail" icon. That thing is like the "push button to walk" at crosswalks. A button connected to nothing, to make you feel like you have agency.
