Here's what I did for Gmail. This solves the problem by limiting the number of messages that are available for your phone/ipad to download. It will drastically reduce the size of your mailbox on your handset (which was my main goal). Your messages are still fully searchable within Gmail, but your Inbox is much smaller.
From your Gmail inbox:
- Type in the search bar (everything between the quotes but not including the quotes) "in:inbox after:1999/1/1 before:2013/1/1" - this will select all messages newer than 1/1/1999 but older than 1/1/2013
- Under the search bar click the check box
- A little yellow bar will pop up saying "Select all messages that match this search"
- Next to the check mark, push the button for "Archive" - this will move all messages between 1/1/1999 and 1/1/2013 from your Inbox folder to your [All Mail] folder
Your phone will now only have messages newer than 1/1/2013. Obviously you can tweak the dates in the search above to suit your needs.
This got me from 9,000 Gmail messages on my phone to about 700.