Hi,
The problem is an organizational one, if you don't trust the exchange in holding the money, the only logical alternative is that a user must make a manual effort to verify the transaction before it is processed. This more or less defeats the purpose of an exchange service that gets its added value because it can act on behalf of the user and large amount of transactions are automatically processed. Otherwise you end up with an ebay for bitcoins.
But perhaps I misunderstood your paper or exchanges in general.
Cheers,
Martin
Still haven't read paper, but exchanges must be trusted, you're giving them your bitcoin so they must be worthy of trust.