This one isn't very illuminating, though, since South Africa malapportioned its legislative seats to strongly overrepresent rural areas, where the National Party was strongest, and underrepresent cities, where the United Party was strongest.
Yes, pretty easy to have happen in Quebec because the Liberals win such huge majorities (90%+) in Anglophone areas even when they lose overall.
Anyway, the clear distinction to make between these systems and the US system is that, in the UK and other parliamentary democracies, voters don't elect the Prime Minister at all. They elect their local parliamentarian, and the parliamentarians in turn elect the Prime Minister. Of course, in a first-past-the-post system, it's very possible for a party to win more votes and fewer seats, but at least there is a clear argument that voters did vote, in a plurality in their constituency, for each person who was elected to parliament and forms government or opposition. This isn't really true in the U.S. presidential system since people don't really vote for electors in their own right (in most states, the electors aren't even on the ballot), and electors don't operate to govern the country in any way except by electing the President.