Dear all,
I got that same error in our exchange 5.5 , we work all day long for this , installing new exchange and member it on same zone, testing are done to this server as we come up to deleting the files under mdbdata folder , which means installing new database both for pub and priv, all contact mails and calendar as well as in the all public folder were erased, its a practical move, instead of reviving the whole database , using the eseutil /p , having the problem on user side, difficult to explain on non tech user, inform the user that your server were infected by virus, and nothing can do about it, than creating new databse for it, this is really works, make sure you backup first the content of mdbdata folder , for your reference, i hope that it would help you guys