There is one idea we haven't talked about yet. Registered mail through the postal service. When Alice sends her money to Bob,she sends it via registered mail. Bob has to sign for it or he doesn't get it. And if he signs for it that makes him obligated to carry out his end of the deal or Alice can take him to court.
The thing about dealing in fiat is that in that part of the deal, recourse means recourse to the court and justice system. Cash doesn't have protocol and executable semantics behind it. That makes it impossible to get a fool proof transaction with it. People do okay most of the time and when they try to screw each other over,that's why the law is and has to be part of the system that includes cash.
You can't make a deal involving cash without recourse to the legal system. The best you can do is to make sure there is evidence to take there.
Conversely if Alice tries to blackmail Bob, the protocol can make sure that there is evidence of that too.
The law works given a chance. Just make sure it has something to work with and soured transactions will be at least as scarce as they are in traditional business, for the same reasons.
Mail will be the primary medium for a P2P market which could follow the exchange project later.
I guess there are forms of money transfers by mail where the amount is registered, so that could be a safe way, but I assume the costs are pretty high and Western Union and such companies will probably be a better choice.
If those services use https webpages where you can track and prove the tx, than it could be used as well with the SSL-log schemes for a secure proof.
If not, a traditional escrow could be used, but has less standardized and safe abilities for a secure proof.
We will probably include a contract where all the trade details are defined and signed by both parties. That is primarly intended for the escrow or for later proof if one party make accusations to the other.
If that contract could be also used as evidence for legal actions is unclear, and as the exchange might be used in bitcoin-unfriendly countries that support is even more questionable.
Also we prefer to build it "self contained" without inclusion of another legacy system (beside banks, mails). But it will be open to the users to use all the available possibilities.