Yes, the solution worked after removing the 2 KB security updates from the machines which were KB2502786 and KB2541025. However, a similar KB2509503 patch was also problematic in a very similar ways to the above patches, so removing either one of the three's (if present) solves this issue, check this thread for better solutions - Excel 2003 documents open slow or do not open.
Bookmarks