Some background I wrote last year on two-party escrow: http://opine.me/future-of-bitcoin-escrow/

I think its a great approach. The reputation system and efficient private search which doesn't require copying the entire database are the hard parts!