Before you do anything, do a backup!!! Maybe do this out-of-hours too.
I found this a long time ago, but only tried it once (it didn't cause a problem). Firstly shutdown the mail store service (it's good to have a batch job do this) - I would shut them all down to be sure:
C:>net stop "Microsoft Exchange Internet Mail Service"
C:>net stop "Microsoft Exchange Event Service"
C:>net stop "Microsoft Exchange Message Transfer Agent"
C:>net stop "Microsoft Exchange Information Store"
C:>netstop "Microsoft Exchange Directory"
C:>net stop "Microsoft Exchange System Attendant"
You may need to shut down some antivirus services - the ones relating to e-mail.
Next, go to the directory where the mail databases are (that's pub.edb and priv.edb). Now run the eseutil, located in WinNT\System32, again, I have a batch job (I've removed some directory structure):
eseutil /g f:\...\pub.edb
if errorlevel 0 eseutil /d f:\...\priv.edb
Restart your services.
Test your mail system.