Archivo ID

Antes que nada, el usuario no podrá volver a leer los correos que tenía encriptados pues cambia su clave de encritación. Eso deberás decírselo al usuario. Espero que no tenga correos importantes que le hayan mandado codificados. Lo mismo con documentos que haya codificado o si tenía claves de encriptación privadas.
Más allá de eso, lo que tenés que hacer es generar un nuevo usuario con el mismo nombre que tenía antes (por supuesto, usando el mismo certificador)
Lo único distinto es que tenés que generarlo usando como servidor de correo asignado tu servidor local. Esto hará que se genere el documento 8y la bbase de correo) en tu estación de trabajo.
Luego de que diste de alta el usuario, podes eliminar la base de correo que se generó en tu estación de trabajo.
Abrí tu local address book, buscá el usuario, abrí su documento en modo de edición, y en el tab Advanced vas a encontrar un campo que dice certified key.
Copia el valor en el portapapeles.
Luego, vas al person document del usuario (en el servidor) y lo abrís también en modo de edición.
Vas al tab Certificates y reemplazá el valor que existe en Notes certified public key por el que tenés en el portapapeles..
Le das el id al usuario, y mándale un correo encritptado desde otra estación de trabajo para verificar que lo pueda leer (por supuesto, escribí algo en el cuerpo del mensaje)