True cold storage would mean they would have had to setup clean systems and generate a wallet addresses only for that machine and its retrospective customer, ensuring that this clean machine never had or would have a network connection to the net.  

My conspiracy theory:

Since I doubt Mt Gox was buying hardware and operating systems to ensure utmost security, they cut corners and probably were using esx and working with snapshots.  Which really was not cold storage because the esx server was online, making it easy for them to open the network bridge to pass the transactions.