En primer lugar tienes que crear una subcarpeta en el outlook express para mover a ella los mensajes de la bandeja entrada, porque si los dejas en la bandeja de entrada y luego los pones en una version superior a la 5 o 5.5 (no me acuerdo bien) no los coje y te deja la bandeja de entrada vacia, perdiendo todos los mensajes de esa carpeta (lo digo por propia experiencia :().
Luego vas a archivo->exportar->mensajes, los guardas donde quieras y cuando lo reinstales los importas y ya esta.
Otra opcion es ir a herramientas->opciones y le das a la pestaña mantenimiento, le das al boton carpeta de almacen, copias la ruta y copias o mueves los archivos (todos) que hay en esa carpeta. Para ponerlos de nuevo una vez reinstalado inicias una vez el outlook, repites los pasos para averiguar la carpeta almacen, lo cierras, y mueves a ella los archivos que habias copiado antes de formatear sobreescribiendo los que se hayan creado. Asegurate si los has copiado a un cd de que no estan como solo lectura y ya esta 
Esto es todo desde el 6, pero me parece que en los otros era igual o muy parecido.
