How would it be organized? Who would make decisions about changing things (the layout, etc)? Who would make decisions about which securities to list and which to avoid (or do you suggest that everything be listed)?
The oversight you make is that unlike bitcoins, an exchange cannot be some homogenous, static, pre-scripted entity. In that context you cannot have it decentralized.
I think you're wrong on that.
In the same way that anyone can write new Bitcoin clients with different layouts etc, anyone would be able to write a new exchange client - only the protocol and specification of block-chain need to be fixed.
Listing also isn't as big a problem as you think. The simplest way (one not involving any Proof Of Stake) is to allow anyone to "list" but allow users to restrict which listings they see based on whose judgment they trust. So anyone could set themselves up as a listing authority - with users able to choose whose judgment (and hence lists of securities visible to them) they accepted. Worthless securities would then not even be noticed by anyone unless there was an approval of them signed and in the block-chain by someone the user accepted as being competent to some extent.
So you might decide you want to provide a listing service, take submissions from new securities and run a website on which you commented on those you considered valid. In the block-chain you'd insert information transactions that proved you approved of (or withdrew approval from) some securities.
I may decide to do it a different way - and run a forum where members voted on which to approve.
Either, Neither or both us might charge a fee to consider applications to us.
Users could either add one or both of us to their list of people whose judgement they trusted - causing securities we approved to be visible in their client.
Users, with a suitable client, could also do things like add 10 approvers and define visibility as being restricted to only those approved by at least X of those 10 approvers.
Decentralised solutions DO exist in concept - the devil, as always, is in the detail of implementation (there's big issues with allowing large quantities of genuine orders whilst preventing spam attacks for one thing).