1) How could MtGox realistically produce "fake" bitcoins? Doesn't the algorithm insist that each transaction be validated independently?
You can't validate balances at Mt Gox like regular bitcoin balances because you don't know at what bitcoin address your money is. This is true for other major exchanges also. Your balance with them is simply an entry in their books/accounting database. This should but may not be backed by actual cash/BTC in their bank account/cold storage etc.
So you can't know if they used your money to pay wages, or pay other users instead of keeping it separate.