What do you mean by "all messages deleted"?
Deleted on your phone? On the server (as seen via Web interface)? On another device/computer?
Do you have other devices accessing the same account? Is any of your devices, including your phone configured to access you email server via pop3?