There is already a working (mostly) decentralized p2p exchange: https://bitcointalk.org/index.php?topic=27055.0

It works more like OTC over a p2p network.