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.