I followed your instructions below and I receive a message 'no messages matched your search' when I performed the search in the Trash box. Am I doing something wrong? Thanks.
you can recover permanently deleted emails even after deleting them from your trash folder all you have to do is open you gmail then click the drop down arrow from your search box at the top of the screen. it will then ask you several question such as to: or from: subject, has words or date with in. don't answer any of these question just click on the blue search button on the bottom left of the search box and all of your deleted emails will be revealed