Comment by setopt

It depends on your provider, unfortunately. If you use their iCloud mail service, search works fine – it appears to have some way to do server-side search for their own email.