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.