For me there is a checkbox next to each message (including the deleted ones), and underneath the list a drop-down containing a list of actions for checked items, including delete and undelete.