Okay, let's keep on working on some other ideas then. Do you have any cached map services in the *.mxd? If so, then it could be a bug (BUG-000107314).
Another option for troubleshooting (in addition to the blog article) is the following:
Open Windows Explorer and go to the following path on your computer and navigate to:
C:\Program Files
(x86)\Common iles\ArcGIS\Desktop10.0\Configuration\CATID
If the CATID folder exists, it will contain files which have an ECFG extension. These files initialize 3rd party extensions that may exist on your computer that were
installed for previous versions of ArcGIS Desktop. If the CATID folder exists, rename the folder as CATID_old. This will disable the extensions.
What is the result?