There are two places to search and they work differently:
- The app's main window (account list) -> searches all loaded messages, and just loaded messages, but looks in all accounts / folders at once
- A specific folder's message list -> searches just that folder, but for IMAP and EWS accounts, will hit the server for older messages (you may need to scroll the list to the bottom and tap "Search for next ... messages").