Have you checked if it’s the fault of your mail providers? The search function queries the remote mail servers in addition to the local cache. If the mail servers return garbage you get garbage results.
Mail search works flawlessly for me with Gmail and Outlook. It takes a sec but the results are always relevant.