Eu usaria o programa ScanPST da Microsoft para reparar os arquivos de dados que o Outlook não reconhece. Este programa deve ser capaz de recuperar tantos e-mails possíveis dos PSTs corrompidos.
Instruções ScanPST: Microsoft ou How-to-Geek
Quanto ao servidor que armazena todos os seus e-mails, isso é difícil de responder. Eu estou supondo que você está usando o Outlook por causa do trabalho. Se assim for, então as chances são sim, existe um servidor com todos os e-mails enviados ou recebidos. No entanto, é provável que o seu administrador ou política de TI não permita recuperá-los através do servidor. Normalmente, esse servidor é usado apenas para recuperar emails de indivíduos por motivos legais ou de investigação, ou para recuperar completamente os emails de todos no servidor após um grande desastre de TI.