If you deleted the messages from the Deleted folder as well, you can try to recover them using the auto-recovery process.more