That is really hard to say without having some configuration information to
work with.
Sounds like you are using an IMAP account. In that case, there is no Deleted
Items folder. Items get marked for deletion and can be "deleted deleted" by
purging the corresponding folder. This purging can be set to occur
automatically upon changing folders and then the message is permanently
deleted and recovery is only possible from a backup.
If the folder has not been purged yet, you can make items which have been
marked for deletion visible by changing you view of the IMAP folder to "IMAP
Messages" via View-> Current View. Right now, it is probably set to "Hide
Messages Marked for Deletion".
