Developers, programmers, where are you? Lets get this thing operational before it's necessary.
It's not exactly a software development problem. An exchange needs to electronically transfer legal tender ($USD, $CAD, etc.). That's not possible without reliance on 'traditional' infrastructure. For example MtGox relies on Dwolla.. I'm not saying the US govt.
wants to kill MtGox, but if they did then that's the weak point. No matter what service or technique you use, if you want to electronically transfer legal tender you will have the same kind of weak point.
The closest thing to a decentralized exchange is manual bank deposits between individuals, but then that's basically what localbitcoins.com is.