Search is great with iOS for the messages you already have, but it doesn't work at all for "continue search on the server". If the Gmail app fixes that, it's a major feature.
“Continue search on server” works for me, although it is slow and the UI is clunky: I have to first navigate to the All Mail, then search for something, then click “Continue search”. I’m sure this would be much easier in a native Gmail app for iOS.