It also serves to illustrate the silliness of the rigid dejure mechanic and another example of game mechanics not allowing things in game to mirror reality (kingdoms appearing and disappearing down the start date timeline but not in game. In what is mostly a great game this is an ongoing issue.
You're exaggerating the extent of the problem. In this period Catholic King-tier titles did not "emerge," they were explicitly created by a Fons Honorum. Every Catholic King-title in-game a) existed in 1066, b) claimed it was merely a revival of a previous title (Bosnia claiming to be Serbia, Portugal Galicia, etc.), or c) was a Crusader state.
Border changes among Catholic King-tier states with recognized borders were basically unheard of.
Which means the system mirrors reality much better then any system that allows you to leave France de jure just because you haven't been an actual French vassal for more then a century.
It's not like Philip IV didn't do exactly that with Navarre in 1284 ...
This is not true. He married the reigning Queen of Navarra, who inherited the title from her father. The Spanish did something very like this creating the title due to owning the de jure territory under Ferdinand II in 1511, but that's out-of-period.
As for Navarra and gameplay, that was very extensively tested. Much of CK1 was a test. The conclusion was it was way too easy to go from Duke to King. Pay a little prestige, nab two Counties, and then instead of having to declare independence you get it for free. You get a prestige bump, desmene bump, the whole nine yards.
CK2 made this easier in a lot of ways. Since you only need half the land, it only takes a claim on one Navarran County to make you a King. In CK1 you needed both. If you're a Duke you don't have to fight an independence war. If you're already a King it's a no-brainer because free prestige.
Nick