I'm considering sorting exchanges not only by volume, but first including those that provide such proof if the idea works out.
I totally support such a motion!
To start with proof of solvency, a daily proof of millions could already give them a small batch of trust. The proof of "my" funds being there is essential to ensure a 100% coverage but not to gain some basic trust. Without reading all at your links I would assume it would collide with cold storage and transaction policies/habits at the existing exchanges to have each and everyone's money separated/provably available or if it doesn't it could be arbitrarily complicated.
Also I would extend your suggestion to not only include a provably solvent (but may next second insolvent with zero money) badge but also provide another badge for provably save bitcoin deposits:
If I proof to the exchange that I have and am willing to trade a certain amount of bitcoins, there should not be a need to let them hold them. Any amount that is not on the orderbook naturally does not (and I think should not) sit on the exchange. In order to be able to quickly trade, traders would still need a way to get their coins there within milliseconds rather than minutes or even 6 blocks. Therefore exchanges could have an incentive to implement off-chain transactions using micropayment channels. With this in place, an exchange could release some (open source) client to their exchange that the user can connect to the exchange and take full control of his trades. This could even work for the orderbook. If the user is disconnected, his offers drop out of the order book. If an order is met, the client has to approve the release of the corresponding amount of bitcoins and if it fails to do so within a second, it would get penalized. This much more complex order book with dependency on external clients would come at a cost that clients that want this security should pay for and maybe it comes at a cost that would require a few slow-down mechanisms like 60s settlement intervals with minimum order volume or a price per minute an order stays on the order book but I guess this would be a price power traders with thousands of bitcoins locked up in exchanges would be willing to pay. Or in other words I guess once implemented, the overhead would not be that dramatic.