Your question is more general than you think. The short answer is that yes, you can trade stocks on almost any US venue and the stock companies need only adhere to their listing exchange's mandates.

However, your questions hint at massive changes over the past two decades that completely remade how stocks are traded. These issues can be seen in US stock markets as well as many other developed equity markets. So... I'll give more background to explain those answers and how they came to be.

Listing Exchange

First, yes: there is a difference between the listing market which mandates financial reporting and often requires a minimum stock price and certain governance standards be met. The listing market charges fees for listing a stock, however that exchange is then responsible for opening and closing trading on that stock every day. That sets the final price (which may affect financial contracts).

Cross-Market Trading

However, stocks can be traded on a number of venues. In the 1960s, Jefferies arose to allow trading of NYSE and AMEX stocks without having to pay fixed commissions to a specialist. As more market makers offered trading of NYSE stocks off of the NYSE floor, this became known as the Third Market.

Some institutional investors also believed they could do better by trading on a venue other than NASDAQ (which was then not an exchange but a collective of market makers). In 1973 they created Instinet to allow institutions to trade with one another. From 1984 to 1988, the regional exchanges began using unlisted trading privileges (UTP) to trade NYSE and AMEX stocks (Khan and Baker, 1993).

UTP was eventually expanded to allow the NYSE and AMEX to trade NASDAQ stocks. However, volumes for UTP trading remained small until around 2000.

Types of Venues

The above changes created three major types of venues:

• Exchanges (like the NYSE and AMEX) which matched buyers and sellers and sometimes had specialists who could stop trading and trade with customers;
• Market Makers (MMs, like Jefferies) who traded with customers and took risk hoping to earn the bid-ask spread or benefit from trends; and,
• Electronic Communications Networks (ECNs, like Instinet) which merely matched buyers and sellers and displayed the order book to attract liquidity.

Competition Blooms

In the early 2000s, the decline of internet companies led to a lot of available programming talent. New high-performance ECNs flourished: They added up-to-date online views of their order book (something exchanges would not offer for years) and focused on quick execution of orders. Market makers also became more automated. The net result is that MMs and ECNs stole significant market share from the NYSE and NASDAQ.

A number of SEC rules were passed at this time which encouraged competition among venues. This included pushing venues to publish trades and quotes, making venues report execution quality in a standardized format, and redistributing fees according to market quality.

Over 2000-2002, NASDAQ split with NASD becoming the self-regulator FINRA and the automated quotation piece become an actual exchange (Nasdaq). Nasdaq would eventually buy Instinet and Island (another ECN) to improve their technology.

Also over this period, the regional exchanges lost almost all of their market share. Now, the regional exchanges are often used by market makers to cross orders or for listing less liquid stocks. PHLX and the AMEX moved to mostly trading options and ETFs; the Pacific Exchange became where ARCA (and ECN the NYSE bought) traded. Other ECNs arose, like BATS and Direct Edge which are now merged (yet still operate BYX, BZX, EDGA, and EDGX).

Don't be sad, though: these changes slashed prices for trading. Instead of paying $100 or more to trade 100 shares as in 1999, by 2003 it was common to only pay $15 for 50, 100, or even 1000 shares.

The loss of market share does hurt, however. Nasdaq has made numerous attempts to hold on to market share like reshowing orders before sending them to the competition (flash orders) or (recently) trying to roll back UTP trading for smaller Nasdaq-listed stocks.

So, from about 2000 onward, the answer to your question "once a stock is listed can it trade on any exchange?" is yes. It can trade on any exchange or at any market maker or ECN that wants to trade that stock. Nasdaq, however, is seeking to change that.

Listing versus Trading

You ask another interesting question: do companies need to adhere to listing requirements of all the exchanges where their stock is traded? The answer to that is no: the listing exchange is the only exchange they must satisfy. However, if a firm displeases their listing exchange and gets delisted, many other venues and exchanges will also no longer trade that stock.

Why do companies not list on the (cheaper) Nasdaq? For a long time, it was because of prestige and because having a specialist on the NYSE ensured somebody would quote a stock after its IPO. Furthermore, the NYSE opened and closed stocks with an auction -- which was much more reliable than just using whatever happened to be the first and last trade. However, Nasdaq has long since attracted enough liquidity and they even have an automated opening and closing auction. I suspect lingering prestige (NYSE's listing requirements are more stringent) explains why some companies stay listed on the NYSE.

Venue Competition Spreads

The benefits of these changes was so large that many other countries encouraged competition from MMs and ECNs. Europe passed the Markets in Financial Instruments Directive (MiFID) which largely allowed many of these same changes to occur in European markets. (ECNs, however, were referred to as multilateral trading facilities, MTFs.)

MTFs like Turquoise and Chi-X Europe arose, stole market share from traditional (listing) exchanges, and also lowered trading costs. Chi-X Europe (now CBOE Europe) has even changed to be a registered market -- so European firms can now list their shares there.

Venue competition has also spread to European bond markets, US options markets, and will likely spread even further.