Question: how to recover the permanently deleted messages?
Answer: Open Outlook.
Select the "Deleted Items" folder.
Go to the "Tools >> Recover Deleted Items from server"
Select the email(s) that you would like to recover.
Click the "Recover Selected Items" button (the icon is an email message with an arrow).
The email will go back to the "Deleted Items" folder it was in.