Just a shot...
If you are using an IMAP connection, you might find that your email server
administrators have the option turned on to hold onto deleted emails in the
background for a certain length of time. I managed a Microsoft Exchange
server for my business and chose to keep users deleted emails for 60 days.
There were a number of times when I got your type of request and was able to
show them how to click on their deleted items folder and then recover
deleted messages. Of course that takes extra storage and backup resources
on their part.
(IMAP is important because POP3 means "give it to him and dump it". With
IMAP, the mail server hangs on to the message for as long as you do so that
the time from when you delete the item, realize your mistake, and get back
to the support team is probably within their retention time frame, assuming
they've got that option enabled.)