I have six mail accounts that I check on with my iPhone, and for months, I've moved read e-mails to the Trash. What I forgot was that the trash needs to be cleared periodically. I regained a couple of hundred megabytes of space by cleaning all the accounts.
To empty the Trash you must enter each account, then enter the Trash and tap Edit. You are then given the option to Delete All. Select Delete All, then confirm the Delete All. A simple tip, but one that may free up a fair bit of space on your iPhone.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20081116090053179