This may seem like a daft question, but are you connecting to POP3 accounts?
If so, are you also downloading emails to a desktop client? My understanding is that the Mail application talks to the server and syncs the current status of mail on the server. If you download to a desktop client and remove the mail from the server at the same time (like most people I believe), the mails will disappear from your phone on the next sync.
You can disable this behaviour on your desktop client. I think that you would need a different mail client to stop this on the phone.
Maybe that helps