first check if your deleted items retention is on.
From the user's outlook goto:
Tools, Recover Deleted items (these menus are from outlook98)
Now since it wasn't turned on, this is how to turn it on.
From the administrator console goto
<site name>
<Domain>
Configuration
Servers
<Mail Server Name>
Private Information Store
get the properties on the above, the top item will be deleted item retention time. Set it to 7 days.
Remember to keep an eye on the amount of free disk space on your server as this will cause the database to grow.
I is also a good idea to set up a bricks level backup:
Install exchange administrator console (from exchange cd)
Install the Backoffice resource kit (from Technet cds, Blue utilities set, Sept99=nt4 Nov2k=win2k)
use the exmerge utility to export all mailboxes to .pst files
backup these .pst files to tape
warning! this will take a wagon load of disk space, count on 1.5x your .edb files.
the 2000 version of this util works the best
it can be used on Exchange 5.5 or 2000
but it must be run from a Win2k workstation + Exch Admin console
the 2k version can syncronize just the newer messages
the 2k version supports command line parameters
Now your @$$ is covered.