Search runs on Gmail's, Outlook's or your email provider's servers, so it needs a connection and follows each provider's rules. If you can't find an email you know is there, try these.
Try these, in order
Check your connection. Search doesn't work offline. On your phone, Couldn't reach the server. Check your connection. means Newton couldn't reach the server.
Clear search filters. On desktop, check the chips under the search box, such as an account, From, a date, Has file or Unread, and click Clear filters. On your phone, turn off any of Unread, Starred, Attachments or Last 7 days.
Outlook: search covers the Inbox only. Newton can't search other Outlook folders yet. Open the folder in Newton, or search in Outlook on the web.
Gmail: Trash and Spam aren't searched. Add in:trash or in:spam to your search to look there.
IMAP: keep searches simple. IMAP servers understand fewer search operators, so plain words and from: work best. On your phone, Newton searches up to 10 folders of an IMAP account for up to 8 seconds; add in: and a folder name to search one folder, or search on desktop, which goes further.
Sign in again if asked.Sign in again to search this account means that account needs reconnecting.
If you see Some results may be missing (desktop) or Some accounts couldn't be searched (phone), one account wasn't fully searched. Try again in a moment.
Good to know
On your phone, search always covers every account. On desktop, you can pick All accounts or one account.
Put - in front of a word to leave it out, and use quotes for an exact phrase.
The full list of search operators works on Gmail. Outlook and IMAP support fewer.