Sent mail is already stored in the sent folder for each user, so that answers your first question.
The second statement about deleted mails does change things though, clearly a deleted message (if removed also from the trash) wont be stored in the users account any more. You may be able to locate it in the backups, or you could use the interception functions to store a copy of all outbound email.
This may be a good place to start:
Legal Intercept - Zimbra :: Wiki