When you delete messages and contacts, the file is moved to the Trash folder. You can recover files from the Trash by opening the Trash folder, selecting the email messages to recover and moving them to another folder.
Messages left in the Trash may be automatically purged, in which case you cannot recover them.