Can I travel between two countries on a "domestic" flight?

There are two correct answers to this question:

No: Any flight that physically crosses a border is an international flight.

Yes: A flight that crosses a border can be treated as a domestic* by the airline and Customs and Immigration Officials given specific circumstances such as Pre-Clearance (Canada->US), or Treaty (Schengen).

*Meaning the flight arrives at a domestic gate/airport and the passengers enter the terminal without restrictions. (Note, Border Officials do reserve the option to redirect passengers to full inspection.)

Using the most broad common definition of the terms, a domestic flight is a flight entirely within one country, while an international flight is a flight between two countries. Therefore, there is no such thing as a domestic flight between two countries.

But whether a flight is international or domestic in this sense is really just a matter of nomenclature, one that relies a lot on the often unclear question of what is a country. (Is a flight between London and Edinburgh a flight between two countries?) What really matters to a traveler is not the terminology, but what rules and procedures apply to the trip, such as:

• What travel documents are required (passport, visa, identification, special travel permit, etc...)
• What inspection formalities (immigration, customs, agriculture, etc...) apply and where are they conducted?
• Does the flight depart from or arrive at a separate "international terminal?" This can be misleading: in some cases, domestic flights may leave from an international terminal and vice versa to make the most efficient use of airport resources.
• What airline policies apply for minimum check-in time, baggage limits and fees, meal services, availability of services like lie-flat seats in premium cabins, etc... These may vary by domestic/international status, but also the length of the flight and the specific city pairs involved.

And the answer to these questions depends on the specific destinations involved. To a first-order approximation, international flights within the Schengen area feel like domestic flights to travelers, as there are no immigration controls. Conversely, some flights that are technically domestic flights might require immigration controls, typically involving territories (e.g. Beijing to/from Hong Kong). Other international flights may involve Preclearence at the destination airport, which typically requires an earlier check-in time, so they may "arrive as domestic flights" at their destination (without further immigration controls). Still other flights may be entirely domestic, but require special formalities, such as government permission to enter a specific area or an agricultural inspection (e.g. when flying from Hawaii to the US Mainland).

The specific case you've mentioned is one where both the ROC and PRC find it in their general interest to maintain that a flight from Taipai to, say, Beijing is a domestic flight, even though the two are controlled by two separate governments. The governments involved officially consider the territory a single country and so will call such a flight "domestic," but if you want to call it "international" in the privacy of your own home (because they sure seem like two countries if you don't know anything about the history and politics), feel free, as long as you don't care what the Chinese government thinks of you. Again, the relevant bit for travelers is what policies apply to Cross-Strait flights, and that tends to involve special travel documents like the Mainland Travel Permit and the Entry & Exit Permit.

Flights between the USA and some airports in Canada are considered "domestic" flights. Likewise some flights between the USA and Mexico, all flights between the USA and Bermuda and perhaps some of the Caribbean nations. But alas no territorial dispute for your criteria 4.

All flights between countries in the Schengen zone are international flights but the rules for domestic flights apply, with shorter check-in, no immigration formalities on either end.

There are true domestic flights, like within France or within Spain, which are just leaving from the 'within Schengen area'.

The three destinations you list are in Taiwan.

There is absolutely no way for any company, in any field, operating in PRC, acknowledging Taiwan as a foreign country¹. For the PRC the official position is that Taiwan is part of China (even if not under their control); they are VERY sensitive about the issue and any statements that goes agains that are anathema.

In a practical level, lately there has been some "defrosting" of relationship between both the PRC and ROC that has allowed direct travel between both (for many decades it was just impossible), but that does not affect the official line.

In fact, any ROC citizen trying to get to PRC with his Taiwan issued passport will be promptly returned to Taiwan (and vicecersa); in order to avoid accepting ROC passports in PRC (and PRC passports in ROC) they must get some "travel documents" that are passports in everything except that they don't imply diplomatic recognition of the other state.

So the only place where you can see those flights is in the "Domestic flights" category because it is where they fit according to the PRC legal theory.

In the end it is up to you to decide if you want to call a flight between PRC and ROC as "international travel" or not.

Glossary (There is always someone who is confused):

• Mainland China: What you think about usually when someone mentions "China".

• Taiwan: A big island SE of Mainland China.

• PRC: People Republic of China, "Red China", the government stablished by the Communists of Mao Zedong after their triomph in the Chinese Civil War. Officially sees the ROC as "Chinese Rebels" to be absorbed back into the PRC. In a practical sense they are well enough with the status quo.

• ROC: Republic of China, the remmanst of the defeated Kuomintang government who stablished themselves in Taiwan. Officially sees the PRC as "Chinese Rebels" to be absorbed back into the ROC. In a practical sense they are well enough with the status quo, although there are some parties that claim that they should declare themselves independents (i.e. a different state) from PRC.

• China: Pick your choice..

¹In fact, not even ROC acknowledges itself as a different country. Both countries claim themselves to be the only "China", with the territory of the other being "held by rebels", even if for most practical matters they act as different countries.