You could enforce some simple rules. Such as require payments into the exchange be made by an "owned" address such that withdrawls will only go back to the same address. And then check any btc withdraw against separate account balances such that people cannot withdraw more than they have on account. And then there is always that thing that Paypal and most other money handlers do - delay xfers for a few days giving time for reconciliation and verification. Given the track record of exchanges allowing instant withdraws I'd think users would be ready to put up with some delay.

But all of this is moot if you keep an unencrypted backup copy of keys anywhere even remotely possible to reach - which makes this yet another fiasco.