Of the eight Great Houses only three have been lords of their domain for a long time: The Starks, the Lannisters and the Arryns. On the other hand, the Baratheons, the Tyrells, the Tullys and the Greyjoys owe their rise in station to the Targaryen conquests (barely 300 years old) that extinguished the Durrandons, the Gardeners and the Hoares. Similarly, the Martells only rose to prominence when they allied themselves with the Rhoynar 500-1000 years ago.
House Stark's reign does indeed date to at least 8000 years (although some Measters dispute those numbers due to the lack of sources) but those were far from being undisputed. The Boltons have been a constant thorn, and at least one cadet branch (the Graystarks) have attempted coupes. The fact that the Starks have remained in power is possibly due to the power sustained by the massive holdings surrounding Winterfell, and the seemingly undying loyalty of the Northmen to the Starks.
On a similar vein, the Lannisters massive ancestral gold mines have kept them rich enough to stay on top, while the impregnable Eyrie has kept the Arryns safe from all aggressors until the Targaryen dragons arrived.