It's pretty straightforward to compute the sum of all coins in your wallets, I would assume. It's also straightforward to compute the sum of all account deposits tracked by your database. Just knowing those two numbers is really simple stuff, like a single SQL query on the DB. All they need to do is calculate those numbers and report on it daily or weekly and they'd have detected the fraud the very first time coins were taken.
(Not physical cards traded online, mind you, these were virtual cards in the game Magic: The Gathering Online.)
They were simultaneously bit by an attack exploiting a fault in their wallet implementation in combination with transaction malleability. You can invert all the bits in a transaction id and if you also take the complement of the signature then the signature is still valid. The transaction still happens but you never see the transaction ID come over the network (it's actually the complement of the txid). After a while, most clients concluded that it wasn't broadcast successfully and either aborted or retry, so their wallet balance diverged. And yes they probably did not check it against the official client balance.
A significant number of frontend nodes participated in this transaction malleability attack over a sustained period of time, probably more than a lone-wolf attacker could access (although renting botnets isn't all that expensive, especially if you are sucking out bitcoin at the same time...)
The interesting question is whether they had someone on the inside, although it could also be explained by incompetence and an attacker probing for weaknesses who comes to realize that the bug wasn't being patched.
> It's pretty straightforward to compute the sum of all coins in your wallets, I would assume.
You assume incorrectly. It's a cold wallet. It's not connected to anything; that is its purpose. To monitor the balance, one would have to write software to watch the blockchain and calculate the balance of specific addresses. This is by no means impossible but in 2011 there were very very few engineers on Earth competent to do it and Mt Gox was trading bitcoins for pennies. Don't underestimate how fast Bitcoin went from a strange curious technology to being worth significant money.
Ultimately you are judging their actions through the lens of hindsight. Best practices weren't even established yet.
There were one or two exchanges that did things "right" (e.g. TradeHill) and were immediately driven out of business by their own high costs.