In the context of this question, it is worth mentioning that there were also two Vietnams and two Yemens; in each case, one was socialist and aligned with the USSR or the PRC while the other was capitalist and aligned with the USA or its allies.
I think, beside the obvious similarity mentioned in the first paragraph, the individual cases are too different to be lumped together. That also means that little can be learnt from one case and then applied to another case.
The Yemens
(I will admit that I know least about the history of these two states.)
The partition came about essentially by historical accident. The entire area had been part of the Ottoman Empire but the British eventually secured what would later become South Yemen as their colony. The Ottomans withdrew after the First World War when their empire collapsed which led to an independent North Yemen. Decolonisation – aided greatly by a Marxist guerilla movement, the National Liberation Front – forced the British out and created the People's Republic of South Yemen which received support from the Soviet Union as a fellow socialist state. The two states were basically the continuation of the previous situation under different colours.
Two short wars later, a reunification plan and treaty was laid out and at the end of the cold war the countries reunited. I suspect that the economic demise of the Soviet Union in the late 80's played a large part.
The Germanies
Germany had been a single unified state (similar to the ones that are discussed further down in this answer) for around 70 years when a certain dictator started a war to conquer new territory in the East to satisfy his racist ideology. It turned out that the armies he was up against were ultimately stronger than his and since he did not believe in surrendering, military defeat had to be near-complete. This resulted in the entire territory of Germany being occupied by the victorious forces. Their alliance was fragile, however, and political difference resurfaced soon after the common cause they were fighting against was defeated. Thus, two German states were formed, either by secret order or unvoiced permission of the respective occupation forces; one capitalist in the West and one socialist in the East.
(In addition, other territories that had formed part of Germany prior to the war were ceded entirely to the Soviet Union, Poland and an independent country. The former two remained with the country they were ceded to, the Saar region would rejoin the rest of West Germany only a decade down the road in a largely ignored minor sidetrack.)
Both states initially claimed to be the rightful, only German state. The West German state (which continued to claim the ceded territories in the East for a couple of decades) saw itself as a direct successor to the pre-war state of Germany, while the East German state considered pre-war Germany to have been defeated and a new state to have been born from the ruins.
Each state was protected by one of the major alliances of the era: the NATO or the Warsaw Pact. Thus, each state was directly protected by one of the two global superpowers (including military bases on its territory) and thanks to various crises in Berlin it was clear that neither superpower was going to retreat in favour of the other – but also neither was going to directly attack the other any time soon.
After two decades of stalemate, the newly elected West German government decided to pursue a new strategy called Wandel durch Annäherung (change by means of approaching), part of which was admitting that it did not control all the territory that it claimed and that there was some other entity there while at the same time refusing to acknowledge that this other entity was, in fact, a state in its own right.
As they are currently on, it is worth looking at how Germany was represented in the Olympics: up until the 1968 Olympics there had been only one 'Team Germany'. Starting in 1968, two German teams competed in the Olympic Games. In football, the situation was slightly different with the national GDR team being admitted to FIFA in the 50's in spite of West German protest (the FRG team had been (re-)admitted before East Germany was).
Internationally, the West German government initially pursued the Hallstein Doctrine. In a nutshell, this meant that the FRG would not recognise or cease to recognise states that decided to recognise the GDR with the exception of the Soviet Union itself. In turn, this meant that essentially only socialist nations (those aligned with the Soviet Union) would recognise the GDR. Which states those were in 1970 can be seen in the map below (from Wikipedia).
As part of the New Eastern Policy (Neue Ostpolitik) mentioned above, this doctrine was dropped in the 1970's (although it hadn't been 100 % strict before) and gradually the GDR gained full international recognition – as did the FRG, which obviously had not been recognised by many socialist states. In the same vein, under the Hallstein Doctrine it was impossible for either German state to be admitted to the United Nations as the opposing superpower would have used its Security Council veto. Only after the doctrine had been dropped both countries could be admitted simultaneously in 1973. They key point is that both sides agreed and negotiated the result.
The most significant cause of reunification was probably the collapse of the USSR (and thus also GDR) economy in the late 80's coupled with the political changes in Moscow that led to the possibility of reunification talks and the 4+2 conference. A number of safeguards were implemented in an attempt to ensure that the reunified Germany would not remilitarise as it had done in the aftermath of the First World War despite the Treaty of Versailles which led directly to the Second World War.
The Vietnams
The entire country had been a (unified) French colony for many decades before the Second World War, when Japan invaded. I'm not sure I fully understand the political state of Vietnam during the war, but both the Japanese and the (Vichy) French acted as colonialists. Local guerillas fought against both colonial powers, aided by China (which, at the time, was also at war against Japan). The Chinese released a certain Ho Chi Minh from prison which ultimately resulted in the communist Viet Minh becoming the main liberation force of Vietnam; their 'home ground' was the North.
After the end of the Second World War, the French wanted their colony back but Vietnam had declared its independence and the Viet Minh were not going to just give it up. This pretty quickly led to the First Indochina war during which France fought to regain control; this war ended with the 1954 Geneva Conference which partitioned Vietnam along the 17th Parallel. Two Vietnamese states were created and France mostly withdrew from their former colony, leaving the United States as the major ally and guarantor of South Vietnam.
While the Geneva Conference had agreed to a ceasefire, communist guerillas began uprising in South Vietnam very shortly after the state had been declared. The United States – which did not see itself bound by the conference's accords as it had not signed – immediately started a campaign against the insurgents which led to the Vietnam War as it is known in the West.
Long story short, the North was aided by Chinese communists and their strategy proved superior to the US one; in addition, anti-war sentiment was gaining ground in the United States which caused them to slowly retreat from the battlefield. Once they had, the South Vietnamese army was doomed and North Vietnam quickly took over and reunited the country under its command.
I am not sure which countries recognised which Vietnamese state, if any, during the 30 years between World War Two and reunification. However, any previous recognition of South Vietnam was then rendered irrelevant.
The Koreas
This history has elements of both the Vietnamese and the German situation.
Korea, originally a unified territory for centuries had become a Japanese colony in the early 20th century. During the Second World War, it was understood that after the defeat of Japan, Korea would be reinstated as an independent nation. The original plan intended an international trusteeship and free elections; until this could be implemented, it was decided to divide Korea into two occupation zones along the 38th Parallel. However, as was the case in Germany as soon as the common enemy had been defeated it became increasingly difficult for the United States and the Soviet Union to reach an agreement, despite UN involvement calling for free elections and a unified Korea. Instead, elections were conducted in the South under US protection while the USSR helped install a socialist government in the North.
The situation was fragile and there had been a number of border skirmishes between both armies before the Korean War broke out in full force in 1950 when North Korea invaded South Korea, conquering almost the entire country. The United Nations intervened with a US-led force which succeeded in pushing back North Korean forces almost to the other end. At this point, however, China became involved in support of North Korea and the front moved approximately to where the DMZ is now. Negotiations were slow but ultimately achieved a resolution with the front line becoming an armistice line.
Before and after the war, both governments claimed the entire Korean peninsula and outlying islands as their territory. As the Cold War continued, the two states started informal, then formal negotiations. They reached a joint statement that reunification must come from within (no involvement of foreign powers), that it must be peaceful and that it should transcend ideologies and instead instead promote Korea as one ethnic group.
The relationship between the two states has since been meandering from better to not so good. Part of the thawing relations was the use of a unified Korea flag at the opening ceremonies of many Olympic Games including competing as a unified Team Korea at some of these Games.
As was the case with the two Germanies, the two Koreas were admitted to the United Nations at the same time (in 1991) and since then both states have been almost universally recognised.
The Chinas
Unlike the Koreas (indeed, unlike any others from this list), the two Chinas were the result of an inner-Chinese conflict. At the end of the Chinese Empire, a short-lived unified Chinese Republic was established (without the island of Taiwan which remained a Japanese colony at the time). Initially, the ruling Kuomintang had both left-wing (CCP-sympathising or -supporters) and right-wing members. In the late 1920's and largely without any foreign interference, a civil war broke out between these two after the right-wing parts of the Kuomintang purged any and all CCP sympathisers.
This civil war was interrupted by the Japanese invasion as part of the Second World War. While the two sides of the civil war could not agree on a unified vision for China, they agreed that it would have to be one without Japanese involvement. However, calling them allies would give the wrong impression; it was more like 'we'll deal with you when we're done dealing with the Japanese.'
Thus, it was no surprise that shortly after the surrender of the Japanese the civil war broke out again. However, the tactics both sides had used against Japan had led to a very different situation in this 'second half': the communist guerilla tactics had proven popular and more effective and the size of the Red Army grew while the Kuomintang had attempted more traditional warfare with more limited success.
In a nutshell, the communist forces were more successful and almost decisively beat the Kuomintang forces on the mainland; the latter retreated to the island of Taiwan. The CCP proclaimed the People's Republic of China with its capital Beijing, claiming control over all of China. The Kuomintang still saw itself as the legitimate government of all of China (they called it the Republic of China) with its capital temporarily relocated to Taipei.
In the United Nations, the Republic of China had been a founding member and, as a 'victorious' party in the Second World War, was offered a seat as a permanent member in the Security Council. By all accounts after their victory in the Chinese Civil War, this seat should have gone to the PRC. However, the United States was allied with the ROC and the beginning Cold War combined with the Red Scare back at home prompted them to do whatever they could to prevent this inevitable occurrance from happening. In 1961, Resolution 1668 was passed which declared the question of Chinese representation an important question requiring a supermajority vote; this allowed the US to continue blocking the switch of recognition – a resolution introduced annually by (communist) Albania and its allies – for another decade. However, with the continued admission of new member states, the majority in the United Nations shifted away from the western nations (including the US) and in 1971 sufficient votes could be collected to pass Resolution 2751 which switched UN recognition from the ROC to the PRC.
It would not have been possible at the time to allow both states into the UN. Both Chinas saw themselves as the One and Only China. Indeed, the PRC government declared that it would firmly object to anything that even hinted at the existence of two separate independent states. If this reminds you of West Germany's Hallstein Doctrine, that is probably accurate. There is a timeline of diplomatic recognition of the ROC to be found on Wikipedia.
Summary
Unlike most of the other pairs of states, the ROC and the PRC never made it out of a Hallstein Doctrine phase. It is the PRC's expressed and practiced policy to cut diplomatic relations with any nation that should begin diplomatic relations with the ROC.
Both Chinas still officially embrace the One China doctrine.
However, both Chinas have been in a number of informal negotiations which are summarised as Cross-Strait relations.
Unlike the non-China cases, the origin of the Chinese situation is internal.
Unlike Vietnam, a mostly decisive civil war victory did not lead to one state ceasing to exist.
Unlike the other cases, one side of the dispute (first ROC then PRC) was seated in the United Nations and even holds veto power in the Security Council.
While the ROC is 'protected' by the US in a similar way as South Korea, South Vietnam and West Germany were, the side protecting the PRC is the PRC itself and not the USSR (or, in North Korea's case, the neighbouring superpower China).
Finally, unlike the other cases there is nobody who would be able to pressure the PRC into accepting any compromise. The PRC decides what it will and will not accept. This gives the ROC very little leverage. Thus, there is next to no chance of any compromise as per the question being reached.
