La verdad es que no sé como funciona en Outlook porque no lo utilizo, pero en The Bat! y en Outlook Express algunos mails borrados quedan guardados durante un tiempo en los arhivos donde se registran los mails enviados y recibidos. Para ver los del Outlook Express hay que ir a: C:\WINDOWS\Application Data\Identities\{xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx}\Microsoft\Outlook Express\ y abrirlos con el bloc de notas.
Saludos.