Fijate 2 cosas:
1 - Que no tenga filtrado la opcion de ver solo los elementos leidos unicamente.
2 - Que no tenga habilitado el "AutoArchivar" en las opciones del outlook y tenga atachado o no un PST que es generado por dicha tarea, si no lo tienens adjunto y si tienes el autoarchivar, pudo haber sido eso.
3 - descartada la opcion de "Recuperar elementos eliminados", puedes revisar en el exchange, si existen politicas de retencion y cuales se les esta aplicando al usuario o ingresando al OWA haciendole clic derecho a una carpeta si tienes el menu contextual de politicas de retencion o tags aplicados, quiza se eliminaron por eso.
Saludos.