Wouldn't it be possible to create some kind of decentralized exchange?
Yep theoretically it can be done. I would imagine it would be in the form of an application or "addon' to the official bitcoin software. It would essentially work like the existing OTC bitcoin marketplaces already in place BUT it would not vulnerable to shutdown because it would not be hosted on web servers.
I've got some ideas as to how this should work. One would be that the addon would operate a parallel P2P network which stores and broadcasts all available bid/ask order (like a stock market exchange but decentralized). After you decide how much you wish to buy your oder would be matched with the best available price for the number of "lots" (how many bitcoins you wish to buy) you want. Then if your order was met by a single person (the purchase CAN be spread across multiple sellers even at different prices if your total order cannot be met by a single seller at your asking price) he/she would then receive in encrypted format payment details and turn you'd receive his/her's payment details. This software could run it's own peer to peer escrow service whereby whatever bitcoins you are due to receive would be spread out across the network and in a sense every participant in the marketplace would own a tiny tiny fraction of your transaction UNTIL the settlement terms have been met - ie you paid the seller. Now where it gets tricky is how do you ensure the safety of the sellers and still allow buyers to use a wide variety of payment methods. Also how do you keep the seller's privacy?
I can think of some ways but they'd be a tad bit cumbersome and open to other risks. There are also tiny technicalities that need to be addressed, such as what happens of the seller decides not to release the bitcoins from escrow. I think that depending on the method of payment used by the buyer the network should automatically release the funds, but since this would require that a certain database of various transaction clearance time frames be stored by the network I think a better idea would be to have it simply expire at 30 days regardless of the method of payment.
Also we would need a distributed user rating/feedback system. This would also have to be stored by the network, but since this would be simple text which can be compressed easily it should not pose too much of a bandwidth burden.
This addon could also use the bitcoin network to bootstrap itself. When it first starts up it would send a request to the various bitcoin nodes it normally connects to anyways asking whether that particular node is running this software and if so whether it is a willing participant in the network - ie whether it accepts incoming connections.
Just throwing out some ideas.