I'll try to answer your question with regards to Canada.
Canada has a constitution that splits jurisdiction over matters between the federal government and the provincial governments. Provincial governments are not considered subservient to—nor do they serve at the pleasure of—the federal government (which is why, in Canada, it tends to be more appropriate to call them two orders of government rather than two levels of government). For this reason, I think it is just as important to consider provincial elections as it is federal, but I can only really speak to a few provinces.
First, federal elections. There were a few that stood out to me when I first read your question, but after looking more deeply at the election results it turns out only one really fits your criteria. From Confederation in 1867 until the 1990s, the Conservatives and Liberals essentially went back and forth as governing party and Official Opposition (the second-place party). There was a bit of an anomaly in 1917 when the Conservatives and some Liberals came together to form the Unionist Party (which was essentially an election about conscription), but the Unionist coalition was gone by the next election in 1921 (technically, the Conservatives came third in that election, but they were still named the Official Opposition due to the leader of the second-place party declining Official Opposition status—and so the largely two-party state continued). In 1945, the Conservatives were renamed the Progressive Conservatives. The two parties would continue to go back and forth.
In 1984, the Progressive Conservatives came to power by winning more seats than any party had/has in any other election before or since. However, the Liberals (whom the PCs replaced in that year) clung to second place and didn't go away. For that reason, I don't think this election qualifies for your criteria.
The election in 1993 was the one that definitely qualifies. The formation of two new parties—the Bloc Québecois and Reform—resulted in a huge collapse of the Progressive Conservatives, who went from 169 seats in the prior election to only 2. There were two major reasons for the collapse:
- The PCs were incredibly unpopular. The former Prime Minister had retired from politics, leaving his replacement (our first and only female Prime Minister) to pick up the pieces.
- The new parties—Bloc Québecois and Reform—stole support from the PCs. Not only that, their support was incredibly concentrated by region. Given how the First Past The Post electoral system works, concentrated support can translate into huge gains in seats (the PCs came third in the popular vote—in fact, they almost came second—but a distant fifth by seat count, which is all that matters). The Bloc were concentrated in Québec while Reform was concentrated in the western provinces.
The Progressive Conservatives would never play a major role in federal politics again, eventually merging with the Reform Party (which at this point had been renamed the Canadian Alliance) prior to the 2004 election.
Although it doesn't really qualify by your criteria, if you want to see an interesting blip, check out the 2011 election. The NDP catapulted into the Official Opposition and the Bloc was devastated, reduced to only 4 seats. The NDP saw massive success in Québec, largely replacing the Bloc. The Liberals flailed under leader Michael Ignatieff, with the Liberals dropping to third-party status.
Provincially, the first province to look at is Alberta. Alberta tends to elect dynasties, which eventually die out and are never or rarely seen again. Any party that has ever been in power has never returned to power once it was replaced (and that dates back to 1905 when the province joined Canada).
The Liberals won the first four elections with a majority every time.
In 1921, the UFA (United Farmers of Alberta) replaced the Liberals. There were some scandals, but this change can also be attributed to the Conservatives (the former official opposition party) splitting into two caucuses and spending a lot of time bashing the Liberals. The UFA targeted their campaign in the right way. They would win three elections—all by majority.
In 1935, the Social Credit came to power. The UFA were obliterated, losing all 36 seats (their former majority). They would never be elected to a single seat again. In one of the weirdest stories of political leaders you'll ever read, the Premier was forced to resign as Premier after being found guilty of seducing a secretary. In socially conservative Alberta, that was the nail in the coffin for the UFA. The Liberals, who tried to run on the success of the federal Liberal Party at that time, weren't able to attract much of the vote (although they still formed the Official Opposition with 5 of 63 seats). The Social Credit would win nine elections (all majorities), governing until the early 1970s.
In 1971, the Social Credit had governed for 36 years and were seen as tired and old-fashioned. The Progressive Conservatives had a charismatic leader in Peter Lougheed, who brought the PCs to power on strong victories in the province's two largest cities: Edmonton and Calgary. They would go on to win a total of 12 elections—all majorities—governing until 2015. The Social Credit formed the Official Opposition in 1971, but died off over the next three elections and never won another seat again from 1982 on. (In 2012, the newly-formed Wildrose Party was expected by many to come to power. The PCs were already being viewed as tired and their leader had retired six months prior. However, a few ill-timed comments by some social conservatives lead many Albertans to go with the devil they knew. The PCs lost traction in southern Alberta but maintained support in northern Alberta, Calgary, and Edmonton.)
The 2015 election was interesting. The PCs were now seen as even more tired. After 80 years of right-wing governance, Albertans elected a left-wing party in the NDP (another majority). This election was about change, and the Wild Rose would have likely won if not for the fact that they split the vote with the PCs. A number of high profile Wildrose candidates had crossed the floor to join the PC party—a decision that would end most of their fates in politics. It's hard to know what will come of the Progressive Conservatives (they went from 61 seats in 2012 to 10 in 2015), but it's very possible that the party will merge with the other conservative party—the Wildrose—once a new PC leader is chosen by the party membership this spring.
The other province I can speak to is British Columbia, although I'm going to be more succinct. In 1991, the NDP were elected after 40 years of almost-uninterrupted rule by the Social Credit Party. Other than the seven seats they won in 1991, the Social Credit would never again win another seat. This change was largely due to a shift from fiscal conservatism to social conservatism, with many moderate supporters shifting to the Liberal Party.
After two successful elections, the NDP were destroyed in 2001, dropping from 39 seats (a majority) to only 2. This change can be attributed to a lot of things, but there were two major scandals involving ferries and bribery that top the list. This election doesn't really qualify based on your criteria, however, because the NDP remained the Official Opposition and have ever since (even bouncing back to win 30+ seats in the three most recent elections). There was an expectation that the NDP would take over in the 2013 election, but the Liberals returned to power.