A few thoughts here.

I really like the collateral-based system.  I think the only involvement from a 3rd party that is warranted is an oracle which forces the final transaction to not be split, i.e. either the payment goes through completely or a complete refund is given.  And this oracle could be one of the parties of the transaction, as long as that key is wiped after signing both the payment and the refund, right?  So any 3rd party seems unnecessary to me.  Involving 3rd parties holds the potential to compromise anonymity unnecessarily, and the 3rd party could prevent the transaction from completing if they wished to sabotage the system.

Reputation systems would compromise anonymity, and would be vulnerable to Sybil attacks.

For irreversible transactions, cash in the mail seems a good option to me.  It also has much better privacy than banks.  There's a Tor hidden service I saw a while back which acts as an exchange where all fiat transfer is via $20 bills in the mail.  I wouldn't be surprised if that site is a scam, but the idea is good if done using P2P and collateral.  Sure, some people will prefer something faster, but I imagine a lot of people will be okay with waiting 3 business days for USPS to deliver an envelope with cash -- a lot of centralized exchanges take a while too (CoinBase took ages last time I used them).

Also, this concept seems easily applicable to a generic marketplace (a la Bitmit) as opposed to just a currency exchange.  I know that's been mentioned already, but I hope that the emphasis won't just be on currency exchange.

Are you familiar with the BitMarket concept by AyrA?  I'm not sure how similar it is, but maybe some of the stuff in that project would benefit this?