Antes de tudo, é fundamental que após as mensagens terem sido apagadas, ninguém tenha compactado o arquivo de dados (pst). Se isso tiver ocorrido essa solução não funcionará.
Ok, o pst ainda não foi compactado, então vamos aos passos:
1 - Feche o Outlook;
2 - Faça um backup do pst;
3 - Abra o pst utilizado pelo Outlook com um editor hexadecimal (eu usei o UltraEdit trial mesmo);
4 - Delete os valores que aparecem na posição 7, 8, 9, 10, 11, 12 e 13 da primeira linha (se não conseguir deletar, altere o valor para 20 em todos esses sete campos);
5 - Salve o pst, agora ele está corrompido;
6 - Execute o SCANPST.exe que vem com o Office e corrija o pst que você acabou de corromper;
7 - Após corrigido, abra o Outlook e veja que as mensagens voltaram a aparecer.
OBS 1: Caso tenha dificuldades para encontrar o SCANPST clique aqui e descubra.
OBS 2: Clique aqui para fazer o download do UltraEdit trial
OBS 3: Esse é um método alternativo de graça, existem diversos softwares que recuperam mensagens de pst, mas não encontrei nenhum free.