Saving/Managing Outlook Messages

We are running an Exchange server on a Microsoft Windows Server 2003 system.  All of our PCs/laptop systems, both local clients and remote desktop users, are using Outlook 2003 for their mail client.  There are approximately 10 of our users who do not want/need to lose any of their emails (sent/read/deleted/moved to specific folders).  Due to dealing with potential issues with customers several years from now, these 10 primary users cannot afford not to be able to retrieve any message(s) at any given time with very little effort.  They need to be able to look in their inbox, sent items, deleted items, and archived folders and be able to find the desired message without concern that it won't be there.

The "Empty Deleted Items folder upon exiting" option is not checked for these users.  They are occasionally archiving their messages which, as I understand it, is moving these messages from the server to their local hard drive.  This is mainly being done by the local client users.  I'm also using the Microsoft backup tool to backup their archived messages to a specific location on the server in case there is ever a requirement to restore them from the server.

The primary question that I have is where the email messages are stored in this environment - either on the exchange server, on the user's PC, or both.  In my research on this, I seem to recall that with an Exchange server, the messages are stored there on not strictly on the PC.

Also, any additional recommendations on how to store, manage, recall the emails of this importance would be greatly appreciated.

Thanks!