Truncated email deleted from server but not locally

One of my users have used truncated mail and only download partial summary which was fine. However, he has now selected to download the full email and the email cannot be found. The email seems to of been deleted from his server mailbox even though he obviously did not tell this to happen. We have searched All Documents on server copy and the mail is not there.Why did this happen?

Thanks