Instead of going to the Trash "folder" and looking for the message to be recovered manually I instinctively search for it using the prominent search bar, though — to no avail. If you have failed to find a message that you know must still be in the Trash, too, relax and rest assured that it is most probably still there.
Gmail just does not search messages in the Trash and Spam categories by default (not even when you are in the Trash category). It's easy to expand the scope of Gmail search to find and recover any message, though.
Search Everything (Including the Trash) in Gmail
To search everything (including the Trash and Spam folders) in Gmail:
- Click Show search options.
- Make sure All & Spam & Trash is selected under Search:.
- Enter your search criteria and terms.
- Click Search Mail.
- Type "in:anywhere" followed by your search terms in the Gmail search field.
- "in:anywhere national park", for example, finds "national" and "park" everywhere, including Trash and Spam.