I’ve found search in Mail.app to be hopeless, and the solutions you see online of rebuilding Spotlight indexing or deleting-and-recreating your accounts in Mail.app aren’t really solutions in my eyes since they don’t fix the root of the problem (or do so incidentally and invisibly). I use Mail.app only because it integrates with iCloud and my iPhone, otherwise I would go all-in on Thunderbird. On non-Apple machines I always use Thunderbird.