MtGox sold coins they did not have in the first place, that's the only reasonable solution to the 750,000 lost coins mystery.
Another simple solution:
They overengineered their deep cold wallet stuff (e.g. splitting keys up and store the parts seperately in several places) and ran on hot wallets/"warm" wallets (keys in office safe) for a long time. Now that they need to access the deep vaults, they are not able to piece the keys together agian, locking up their old coins forever. Think of it like restoring a RAID-5 and a second HDD failing while the restore is running...