Searching from a particular folder's message list will (for IMAP / Exchange accounts) hit the server for old messages, after doing a local (on-device) search.
It pulls them in a limited number at a time, so yes, you will need to keep pressing "Search for next NNN" at the bottom.
This will only search that particular folder.
Searching from the account list or smart folder only looks in already loaded messages (but searches them all at once).