Deleted email messages are stored under 'Trash' and can be restored by a space administrator from the Space Administration screens.
You can only restore an email message from trash if it was deleted individually and not using the 'Remove All' operation.
To restore mail: