Exchange 2000 Local Message Queue

Having a problem with the local delivery of some messages through our Exchange server. Messages are just stacking up in the local queue and not being delivered.
Event viewer, application tab is showing some scary errors:
EventID: 474, Source:ESE, describing failed verifications with checksums on pages in priv1.edb (private mail store database) and suggesting that if these errors continue to recover the database from backup.
I would like to run some checks on the DB with the ESEFILE /S and ESEUTIL /g tools but all the literature says not to unless in conjuction with the Microsoft PSS help desk.
It doesn’t affect all users and I am loath to rebuild the database unless abolutely necessary. Do the other Techs out there have any ideas?

Cheers Scott