At that point if all the Microsoft Utilities like ESEUTIL or ISINTEG have failed, the client has no choice but to send their corrupted Exchange priv priv1 edb stm to a data recovery company.
How To Create A Blank Clean PRIV1 edb for Microsoft Exchange Server
The Exchange Information Stores are located in the MDBDATA folder (unless you have moved them to a custom location), usually on the second partition in a 2 partition Exchange Installation. In most cases the Information Stores Services are already shut down due to the tragedy that brought you to this page. If not, stop the Information Stores Services.
Now you will be able to rename the MDBDATA folder to something like MDBDATA-old or whatever you want. Now create a blank MDBDATA folder, go back and start your Information Stores Service.
At this point you can go into your Exchange Administration right click on the Private Mail Store (priv1.edb) and click “mount”. You will get a nag screen that complains about there being no edb and life will come to an end in the galaxy if your not careful, but ignore all that and hit OK. It now creates a brand new PRIV1.edb and PRIV1.stm file! In Exchange 5.5 there is only a PRIV.edb, but this works in version of Exchange, the only difference is that in 5.5 it pulls the user list out of the DIR.edb as opposed to the Active Directory in 200x.
That is all. Your users will have empty mailboxes, but at least they can send and receive mail until your Exchange data recovery company can return your mailboxes back.