To recover old emails I restore PRIV.EDB to a test server running Server2000 with SP4 and Exchange 5.5 with SP4 and all required fixes post SP4 for exchange. These data bases always restore as being in an inconsistent state. To fix, I run ESEUTIL/P /IS PRIV.EDB. Since these are large databases, typically 60 GB - 90 GB, this take 18 to 30 hours. The last two PRIV.EDB files I have tried to repair, aborted with the message Operation terminated with error -1017 (JET_errRecordDeleted, Record has been deleted)". . This happened when the database scan was complete and the database repair started.
The event log for the application shows a warning message from source EXE97, event id 136---- (1356) the database engine has lost 1 page of bad data. These messages appear 1 or 2 per second for about the last 80 minutes of the ESEUTIL/P utility run. The first 12 to 16 hours run without errors in the event logs. There are no corresponding events in the SYSTEM or SECURITY event logs.
BTW - I used VERITAS NetBackup 3.41GA to perform the restores. Backups were done under a variety of versions of the same software 3.x - 3.4