We've had a mailbox exchange server of a client suffer a major hardware failure. After sorting that out by swapping out the box we were left with the nice task of getting the stores back online. Surprisingly enough Windows 2003 was still in a decent state after 10 blue screens.

Anyway, things that helped me were:
http://technet.microsoft.com/en-us/library/21187433-f127-4e7a-898a-6bdb34d7a6bd.aspx
To understand that a 551 error and a 1216 are almost identical. http://support.microsoft.com/kb/296843 to figure out which log files were needed to get the stores consistent again. Eseutil /cc to get the log files played back into the stores.

Still means we need to take a good long and hard look at the way we backup our exchange enviroments. Looks like our software once again dropped the ball just like I experienced earlier with an authoritive restore of a domain controller that didn't work and where I had to "touch" objects enough times to get the USN of the object I was trying to restore high enough .