Now before you start laughing, I say this in full seriousness. Several times now I've been asked by users why their old e-mail is being deleted. After a few days/weeks it magically disappears! The solution? Click the right-pointing arrow at the top right of the page labeled "Next Page" and *poof* it's back!
No, I'm not making this up.
One thing that I've noticed with many mail clients is that they'll show the total number of messages in the folder, like "1-25 of 200". The default skin only says "1-25", and this seems to lead the user into thinking they only have 25 messages and the rest have been deleted.