Search has gotten really bad in MacOS Mail.
Even Outlook on my iPhone finds them all right away.
I use MacOS Mail on my MBP because I can use MsgFiler to file and I like the photo annotation feature.
I use Outlook on my iPhone because the filing is better than the really bad one in standard iOS Mail. At least you can search for a folder to move messages to.
But the Mail search in MacOS Mail has become unusable lately.