Is it possible to verify or audit an exchange to determine how much bitcoin they have on deposit? Is it possible to verify or audit an exchange (for eg. mnt gox) to determine how much bitcoin they have on deposit?

For example, they could publish one or more bitcoin wallet addresses and by examining the block chain the total amount of bitcoin held could be verified.
If they want to publish this information, it's certainly possible.

If they don't, nobody really knows. They have at least one Bitcoin address for receiving money from each customer, and probably many, many more. Knowing and tracking all of them would be impossibile.