iPhone ate my mail

Deleted mail was mysteriously disappearing from my email account. I could not find anything older than one week. The culprit turned out to be iPhone. I use it to read the same account. A well-hidden setting removed deleted messages.

To check your iPhone:
  1. Go to Settings > Mail, Contacts, Calendars.
  2. Select the account from which deleted messages are disappearing.
  3. Go to Account Info > Advanced.
  4. Under Deleted Messages, change Remove to Never.
  5. Go back to Advanced.
  6. Go back to Account Info.
  7. Click Done. This is important to save the setting!

My removal interval was set to After one week. Gotcha!