The exchange client uses wallet plugins for different currencies, right? So it should be able to directly verify node balances locally (on the user's computer).

But assuming that the wallet data is false because the client is compromised, honest clients can confirm it's true balance by compiling it's history of transactions in the blockchain.

If you want to get really fancy, the client can generate a ledger of it's own that associates the blocks in different blockchains as parts of the same transactions.