Fully decentralized would mean any two users may meet at any time, and there is an efficient method of advertising (bids, asks) and meeting in the middle (transacting).
Um, maybe. It depends on how you define "decentralized". But, of course, there is a whole spectrum of solutions from a handful of large providers to full p2p with millions of nodes. (Which I would call 'distributed', maybe.)
Somewhere in the middle there is a federation of order book providers with a significant number of members. I would liken them to mining pool operators (which are numerous), thus it might be "decentralized enough" for Bitcoin crowd's taste.
Full p2p would be cool, but it has numerous problems.
Creating your own exchange, due to lower barrier of entry, simply means it is less centralized. As you can see with, e.g. MtGox, being able to start your own exchange does not imply lack of defacto centralization.
Not quite the same thing: there is much higher barrier to entry for exchange which deal with USD, and also an exchange like MtGox holds people's money, which creates a trust issue.
But I would agree that a solution with completely independent order book providers is far from perfect. But much better than what we have now...
Perhaps a federated protocol won't be too hard to implement...