Update: I have now reinstalled all three Exchange Servers by:
Shut down exchange services -> copy database files -> shut down VMs -> reset computer accounts in AD -> install new VMs (sysprep'ed) -> join to domain with old servers names -> copy databases to new VMs (same locations) -> run Exchange 2010 SP1 setup with "Setup /m:RecoverServer /InstallWindowsComponents".
Exchange Management Console and everything else now works again.
Keep in mind that the only thing changed here is the local machine SIDs as I reused the old computer accounts in the domain and they still have the old domain SIDs in the objectSID attribute. No doubt in my mind that the new SP1 EMC is searching for a local machine SID and not the computer account SID in the domain.
@Little Ghost: Thanks for uncovering the duplicate SID issue
@Speights: Thanks for confirming and no you could not use NewSid in stead. It's unsupported and corrupts Windows 7 + 2008r2. Sadly - because I used to love that little tool - but we will have to stick with the more heavy and timeconsuming sysprep tool.
@GT: You're right - sysprep is the only way to go. Sorry if I offended but I am still of the opinion that behind this is a programmers late night decision to solve one problem (the dot in Netbios names KB981033) and instead cause several others. He probably used the machine SID because it was easier than doing an LDAP search and his Netbios / DNS routine didn't work in some scenarioes (so a dot in a Netbios name is probably supported - weird). Luckily he can just relax and say that the now failed scenarioes are officially unsupported by Microsoft. If he had done his job well he would at least have put in a check for duplicate SIDs in the prerequisites checker and let the wizard fail with a nice explanation.