So if a plateau is not formed as originally lowlands forced upwards by nearby mountain-building, then how does it REALLY form?
There are several different processes at the origin of the plateaux in the map you link.
Some, such as the Deccan and the Columbia plateau, are the results of infill of volcanic rocks in an accomodation space during voluminous volcanic eruptions, called "flood basalts". These flood basalts effectively flow into topographic depressions, thus flattening the topography and resulting in a plateau. Note that there are also oceanic plateaux which are formed by large magma outpours- they are usually below sea level. Examples of this are the Caribbean Oceanic Plateau and the Ontong-Java plateau.
Other plateaux such as the Altiplano and Loess plateau appear to be a result of basin infill by mainly sedimentary processes, either by water or wind transport. Past erosion removed material from topographic highs and dumped it in topographic lows, thus flattening out the relief. This is effectively a peneplenation process operating locally.
Although the high elevation of the Tibetan plateau is undoubtedly due to tectonic uplift, the cause of flat topography appears is likely to reflect relief reduction by combined erosion and deposition as above. It is unclear whether this was an ancient peneplain which was pushed upwards, or a more recent feature.