This may not be the problem, but start by right-clicking on the Sent Items folder from the users account, choose properties, then the FIND tab. Check to see that the Date Range filter isn't active ("created or delivered between:" isn't checked) and also check the Advanced Find screen to make sure the user hasn't inadvertantly set a filter on date ranges.
Then check Tools/Options/Send. Look at the Mail tab and make sure "Create a Sent Item to Track Information" is enabled and that "Auto-delete Sent Item" is not.
Hopefully it's that easy to solve.
Dennis