Yep, have exactly the same problem on my ipad and iphone. I googled around, and apparently its not supported yet on exchange. A workaround I used for a while was to set up my gmail on IMAP and exchange. Then I just made sure the IMAP account was receiving only mail, so i could search on the server, and the exchange account only did my contacts and calendars, so i could get over the air syncing. It worked ok for a while, but got a bit messy after some time, so I'm just using the exchange account on its own, and just have mail show more messages, and sync from further back. But its an annoying thing fo' sho'