they all (supposedly) are, the question is how do they prove it so everyone can see for himself at any time
By using some sort of open, transparent system to see where the coins are. Like a public ledger...
I think the problem being asked here is valid but highlights a core problem with Bitcoin exchanges. They aren't. They are deposit accounts with exchange attached. Really you shouldn't be holding any coin on the exchange, you put up your bid/ask, make a trade then complete the transaction within a time limit, possibly off the exchange. Maybe a clearing house to track and followup on trades can back this up.