Wirelessly posted (Mozilla/5.0 (iPhone; U; CPU iPhone OS 3_0_1 like Mac OS X; en-us) AppleWebKit/528.18 (KHTML, like Gecko) Version/4.0 Mobile/7A400 Safari/528.16) Looks like the search on server does not work. I set up the push gmail through exchange. I than selected my all mail folder and tried searching with the search on server option, but no results come back. I think this is one of the most important features. Hopefully google implements it.