Anyway, things that helped me were:
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 .