Did you look in the Deleted Items folder? If they are not there, and if
you (or Outlook) has not yet compacted your message store (i.e., PST
file), you could make a copy of that file (as a backup) and then corrupt
it and repair it to see if the delete-marked items become available.