What is the definition of a P2P exchange? Bitcointalk member BTCLuke suggested the following six criterion for a P2P Exchange: 

A P2P Distributed Exchange MUST:


Be without any central points of failure, since a government or two WILL be coming after it one day. I suggest a Bitorrent-like software schematic.
Show everyone a very large number of possible trades to choose from, (thousands?) so assets can form a stable price. (e.g. a Bitcoin is going for $120)
Transact trades pretty much INSTANTANEOUSLY, so when you're watching a graph and want to trade at a very specific time you can do so. (This is extremely important for arbitragers and other traders who help keep the price fluctuation down.)
Offer Graphs and APIs for for graphing like MtGox does.
Have three-user (trustless) trading, so a non-interested 3rd party always hosts the trade between the buyer and seller. (And should provide Escrow too!)
Hold and transfer IOUs without the need for trust


Does there exist a whitepaper or open sourced project that has a solution for all six criterion? Furthermore, who in the community has been working on P2P exchanges and what regulations would impact them?
Decentralized peer to peer exchange of digital currencies to/from fiat currencies will always have the following constraints:

Fiat currencies cannot be encrypted and represented digitally by a decentralized entity/organization/system. Therefore, fiat currencies will always need to be transferred between traders through the banking system or physically using cash.

Peer to peer trades of fiat&lt;=&gt;digital currencies will always depend on trust. A peer to peer exchange protocol could easily ensure that one party would always send the Bitcoins. The transaction can be verified. The protocol could safely hold the Bitcoins until the other party sends the dollar (Decentralized escrow). But the protocol can never confirm the dollar transaction. It can never know for sure that the transaction has occurred. This introduces the below:



Who's going to send first?
I sent the money. No he didn't
Who will this person be that I'll receive a transfer from? Is he a criminal? Are the funds stolen?
What if this person tells his bank that I fraudulently received this payment.
I went to the cash exchange and had to confirm the transaction at gun point

Remember that transactions  within the banking system are monitored, they can be reversed and funds can be frozen.
I have studied all projects aiming to accomplish a peer to peer decentralized exchange:

Dark Exchange
BitcoinX
Ripple - which is actually a payment system that will hypothetically allow trades as well.

I haven't seen a solution for the above mentioned constraints. All of these projects will be bound by them.
Ripple protocol proposes to allow dollars to be represented on the network and allow peer to peer transfer of dollars, therefore enabling btc-&gt;dollar trades. However, their model depends on Gateways -the entry/exit points of fiat currencies to the network. Users will still need to trust that these Gateways will actually hold and be able to pay the amount of dollars within the network as/when needed. There is no guarantee that these Gateways will not fraud the network or individuals. Neither is there a guarantee that the governments will not shut them down. (Read the first line here: https://ripple.com/wiki/Gateway_List)
My view on the future of fiat=&gt;dollar exchanges:
First and foremost: The significance of exchanges will diminish as the adoption of Bitcoin grows. The less the need to trade your Bitcoins, the less important exchanges are. I truly believe this.
Are you saying that we not need exchanges? Absolutely not. No matter how much the adoption rate grows, there will always be a need to trade Bitcoins -this will be true for at least our  lifetime. So we need better and more exchanges.
So what's it gonna be? A ton of local options for people to buy/sell Bitcoins and lots of big exchanges that local shops can trade with. You need to remember that currency exchange does not always have to be in continuous double auction format. When you go to an exchange office and buy euros with dollar, they are not actually matching that with another order. They put a safe profit margin on the price and we pay it. See: CoinBase
Overall, I truly hope that I'm proven wrong. But I don't think a peer to peer decentralized exchange can be built.
Important last note: All of the above are true only for fiat to Bitcoin exchanges. A digital to digital currency exchange can be made peer to peer and decentralized given that both allow peer to peer public transfers and both are decentralized. (Ex. Litecoin to Bitcoin)