Resolved! Uninstall Symantec EV Version 7
One of our customer has EV version 7 installed and has recently upgraded to exchange 2010. There EV data seems to be mostly corrupt so they are looking to get rid of EV. They don't mind ingesting the mail back into exchange because sooner than later...