The Message menu options related to deleting and restoring messages are:
If you have specified the Hide messages marked for deletion option in the Mail Preferences window, all messages marked for deletion will be removed from the Folder Contents listing. You can restore (undelete) these messages before performing a save changes operation by choosing the Undelete -> From list ... option (see below).