A search of the Apple forums and several other sites all found the same two recommendations to fix search issues in Mail:
  1. Rebuild the Spotlight Index
  2. Rebuild the mailboxes
But if you are unwilling to do that, another option would be to try a different email client. Spark is an App Store editor's choice that has been around for a long time, I have used Airmail 3 for years with no problems, and there are a number of other options on the App Store including Microsoft Outlook.

If we knew what it was we were doing, it wouldn't be called research, would it?

— Albert Einstein