I ran into the same situation. I tried several things before I realized what the problem was. I was trying to search all my email under the inbox and since I archive most of my mail, I didn't get that message to continue searchng on ther server. I beleive it's because the iPhone mail app had already downloaded all of my inbox emails. I went to All Mail and searched again. This time I got the message to continue searching on the server. I hope this helps.
You are correct. I had all my 'Inbox' messages synchronized with my Iphone and there were no left messages to search on that folder on the server. Once I switched to 'All Mail', I got the option. Now let me move all my messages back to Inbox... :P