There are lots of ways to lose emails unknowingly. Without knowing all the details, here's what I frequently see...
1. User goes into the All Documents folder and deletes from there, thinking they are deleting a copy of what is in another folder.
2. User goes into the Sent folder and selects message to delete and chooses the DELETE rather than Remove option. Delete will erase the sent email from all folders it has been copied into, where as Remove only erases it from the SENT folder.
There are probably other issues that more experienced can explain, but the 2 above are pretty common for my users.
Hope that helps.