Sometimes I can't, and sometimes I can. I want to be able to
⌘-Z after I accidentially delete a message. Or multiple messages. I want the
For what it's worth Mail.app can undo deletions but it's limited. It can only do one undo and doesn't work on some accounts depending on the server's IMAP implementation (for example GMail accounts tend not to work). It depends if the server allows Mail.app to undo the IMAP action and whether or not the action has occurred on the server.
If you use IMAP with gmail...
Go to settings and then to the IMAP portion of the settings (it is currently called "Forwarding and POP/IMAP").
This will keep Mail and Gmail from immediately deleting (forever) any mail you delete. Then choose either archive the message of move the message to trash.