A melhor maneira é obter o controle dos e-mails antes de serem excluídos. Vou discutir em geral e aponte para exemplos para o Exchange, porque esse é o sistema de correio que eu conheço melhor.
1- Obtenha os emails do servidor e um arquivo de algum tipo quando eles forem criados. A solução específica depende do seu servidor de e-mail ... GFI e Sherpa estão entre muitos disponíveis para o Exchange.
2- Eu gosto da ideia do IMAP (comentário de Robert Moir para este resposta). É ainda melhor se o servidor de correio puder manter os itens excluídos por um tempo. O Exchange tem uma lixeira de "nível 2", uma na caixa de correio do usuário e outra acessível apenas pelos administradores do servidor. Você terá que se certificar de que o servidor tenha espaço em disco suficiente para suportar todos os e-mails dos usuários, mas o disco é barato.
3- Você também pode usar o arquivamento do Outlook, principalmente se puder controlar as configurações centralmente. Se você tiver o AD, isso é fácil de fazer com a Diretiva de Grupo. Configure o Outlook para arquivar diariamente em um local de servidor central e inclua esse local em seus backups noturnos. Você também pode ter uma "rotação", movendo-as todas as noites para vários locais, para que você tenha várias versões em caso de mau comportamento.