SID changed on exchange, trust is broken between AD and exchange

So what are the errors you're actually experiencing, and how have you established that your migration changed the machine SID? I ask this because if it has, this is the first time I have seen this happen (simply moving a VM from one host to another doesn't, or at least shouldn't do this), so my first thoughts would be to look elsewhere for what the real problem actually is.

As for your recovery options:

Changing the SID makes me uncomfortable on an Exchange Server. Even if you can establish that this is the fault and change it back without causing a crash then I'd be unhappy to continue using that server. The other proposed solutions don't fill me with joy either (possibly because I don't understand what 15 dotnetnuke servers has to do with exchange)

At this point, I'd maybe see if I could add another mailbox role server to the exchange organisation then attempt a move mailbox. If that works then all should be gravy. If not then (this may scale badly depending on number of users, but its "dumb" enough to work pretty much no matter what) consider exporting mailboxes to a PST and then importing to a new mailbox server.

Edit

Just as a point of interest, what happens when you run the exchange best practices analyser on that server (and if present, another exchange server in the org)? That might shed some light on what has happened, and if its a common scenario then Microsoft are pretty good at linking to useful knowledge-base articles directly from the exchange BPA reports.

Secondly, just a silly point, you have checked all the usual name resolution of DCs is ok, that the time/date/timezone are correct, etc (seriously, time getting out of sync can be a big problem with virtual machine guests, and the time being wrong will make active directory pull a sad face when exchange tries to talk to it).

As others have said, a P2V or V2V migration is not supposed to change the SID of the migrated computer, for the exact reason you're experiencing: it would not be anymore a working domain machine after completing the process, and this is not only a trouble for Exchange, but for anything running in a domain environment. So, unless someone or something ran Sysprep or NewSID or whatever on the machine, its SID should not have changed at all. Out of curiosity, how was the migration accomplished exactly?

That said, determining if this actually is the source of your problem is fairly easy: just have a look in the computer's event log for Event 5513 from the Netlogon service, as described here: http://support.microsoft.com/kb/150963; or for any other domain-logon-related errors: there should be plenty of them, if the trust relationship between the computer and its domain has actually been broken. If you can't see any, then a changed SID is very likely not your problem.