I tried running a search on their inbox but don't see anything there.
I checked Mail Retention policies and size quota. Nothing there that would trigger this.
Is there any Windows or Exchange server logs which would show how these emails were deleted? The user is syncing emails with both an Android and iPhone so maybe some settings on those phones removed the emails?