I'm also using Mail.app right now and I've been having similar issues with search and stuff. Does anyone have any recommendations for good desktop email apps on macOS?
In the end I went with Mailmate and I’m extremely happy with it.
https://en.wikipedia.org/wiki/Mutt_(email_client)
Depends on your definition of 'desktop', of course ;)