I set up Gmail on iOS as an Exchange account and server side searching works for me.