Hi,
Is your account type IMAP or POP3? What mail service is it? (e.g. gmail.com, hotmail, etc.)
Are you still using another mail app on the desktop?
If so, is it set to delete messages from the server after checking mail, perhaps (a frequent thing with desktop mail apps)?