Yes they should. A deposit liability arises from the fact that they received an asset in a deposit transaction. Liabilities and assets aren't mutually exclusive in any transaction, and both must increase when you receive a customer's deposit, or else where does the liability come from?
> Banks need to be heavily regulated because they are investing the assets of their customers. An exchange should not be doing that, it should be holding customer assets and making them available on request.
If the exchange doesn't spend assets they received from their customers, they still have assets. If they sit on them until they receive instruction from a customer to dispose of it, it's still an asset on their books until they carry out the instruction.