Recover Deleted Items Exchange 2003 / Windows XP Pro

I got an email from one of our customers who is having some email issues. They have a windows 2003 Domain consisting of 1DC and no member servers. Exchange 2003 is installed on the DC. They use Exchange even though there email is provided by a separate company that is also hosting their website. When they send emails to each other, the traffic gets delivered locally through Exchange. When they have email going out of the local network it gets sent to the Exchange POP3 service and forwarded out using their hosted email address.
According to them, some users have limited access to recover deleted items, meaning that after deleting an item from the Inbox and the deleted items folder, it can sometimes still be recovered using the menu but other times it cannot. As far as they can tell, it is a totally random phenomenon and the non recoverable emails have nothing in common. Some users, however, have no luck at all getting any emails to recover.
This is a pretty small network and all user accounts are in the same OU, they all reside in the same mailbox store, and there are no custom policies applied that would affect recovery of deleted items. No settings have been applied exclusively to a group of users or computers. At both the Domain, OU, and Exchange levels, policies are applied universally. I know the previous sentence to be true because I documented the Server settings when they started using us. I will be at the location later today to try and figure this out for them and to see if I can find a commonality among the 2 different groups of emails that they may have missed. If anyone has witnessed this behavior before, or has a better idea where to start than I do I would appreciate the input!