Most of us watch a consolidated tape, as per chartman, so non-best trades can happen from some upstair/dark pool/offline trade. If you are watching a specific venue's book, like NYSE, then expect to see plenty of NYSE registered stocks being printed based on the book of other exchanges. NYSE talks at length about their complex market maker system to keep a tight spread. Wouldn't be a point if you can get the same price everywhere else.
Another possible cause, honestly, is exchange error. I have called to the trade desk on a number of exchanges after having thoroughly researched the regs. The guys on the trade desk are there to keep things moving without incurring exchange liability, not to get things right. I can completely understand when a rep gets an answer wrong initially. Once reminded of the regs, there should be an "oh yeah, I studied that" moment. If I want guess-work, I will ask a broker.
As far as Bob111's objection to 50+ market centers for US equities instead of 2. It is about innovation, payment for order flow, transparency, and product differentiation.
Innovation. ARCA is now a growing part of NYSE's business. Before 2006, it was Archipelago Exchange an innovative competitor. In a classic buy vs build, NYSE bought.
Payment for Order Flow/Liquidity. It is here to stay, and every broker wants to make sure that they get as many cuts of the pie as possible. If there were only one exchange, how could your agent getting a piece of your losses?
Transparency. This actually works both ways. Big orders will always try to hide. Its perfectly legal to use iceberg orders, lump all of the limit orders under the Market Maker ID=NASD, and other concealment methods. On the other hand, if my memory serves, Google bought a more-or-less defunct ECN so that they could get ahold of real-time trade data without exchange fees. This led to the creation of a flat-rate monthly fee structure which allows us to get real-time quotes on a number of sites, including Google.
Product Differentiation. The exchanges don't do the same things. NASDAQ has an elaborate opening/closing process with simulated execution whereby their market makers are solicited for On-Imbalance orders. This is particularly important if you are an ETF which needs a large index-change fill that everyone and their brother is trying to front-run. NYSE emphasizes that their local/captive market makers follow rounds akin to LME to minimize the bid-ask spread. All of these exchanges differentiate themselves in some way.
I have dealt with governing bodies long enough to understand that if your choice is between excessive meaningless product differentiation and obstacles to innovation, put up with the product differentiation.
