Hola:
Hay un programa que te permite migrar todos tus correos antiguos a Gmail. El vínculo, a día de hoy, es
http://tools.google.com/dlpage/outlookmigration
Una vez en Gmail son recuperables por la aplicación de correo que tengas en Android y podrás hacer las búsquedas normalmente.
Para hacer otro tipo de apaños puedes probar a importar el correo con Thunderbird (sí lee los PST) y reexportarlo con otro formato.
Espero que te funcione.
Un saludo.