Message searching for Gmail in Outlook iOS/Android is piped directly from Gmail itself. Your search is forwarded on to them and results are displayed back in the app. Immediate search results are from on-device and then filled with the Gmail results after they are received. So if the results are bad, then maybe Gmail has a secret API they use to make their app better.