The precursor to the modern Proficiency Bonus method was introduced in 3.5e's "Unearthed Arcana" under the idea "Maximum Ranks, Limited Choices". Though at the time it still had "Cross Class Skills" at half-proficiency. Though arguably you could also say it came from the very next option (on page 81) of Level Based Skills, where you picked your proficiencies at level 1, then just used your Level as your Proficiency Bonus rather than having skill points at level+3 maximum.
First, this was a very obscure option in a corner of only 3.5, and while it adresses the choice of skills at level 1 and not having points to add, it does not touch the main game changers in skills in 5e, the bounded accuracy and use of advantage/disadvantage.
Moreover, this does not date back to 3e, but this was already present in AD&D 1e, in the dungeoneer's survival guide: "All characters start play with a number of proficiency slots at 1st level..." The only difference is that, like everything before 3e, it was reversed as it did not yet benefit from the d20 unification, which was one of the major breakthroughs of 3e.
In either case, you picked your skills at level 1 and they leveled up automatically with you, rather than getting different levels of skill point expenditures on different skills. The only ways to get more skills were Skill Granting Feats or increasing your Intelligence modifier.
Which, you are right, I forgot as a very crucial change in 5e (and a bit of a shame, if you ask me, as it really lowers the value of intelligence, maybe the solution lies into allowing intelligence to gain you some expertise, or half-expertise), but still minor compared to BA and Adv/Dis.
4th Edition took that option from 3.5's Unearthed Arcana and ran with it, making it the default with players adding 1/2 their level to any skill in which they were proficient instead of your level or level+3 or full level.
Indeed, but still not addressing the two major game changers above.
5th Edition took -that- and added in Bounded Accuracy (since AC in 4e also went up with your level) to streamline it and make sure even a puny kobold had the chance to roll a Stealth Check that beats your Perception check. They did this by shrinking the proficiency bonus even further.
And this is absolutely critical, much more than the number of skills or having only certain skills maxed out, because exactly for the same reason, it allows almost any adventurer a chance to succeed at almost any skill check or, the other way around, allows any adventurer, even a very skilled one, to fail at even fairly easy tasks in his chosen domain of expertise.
This is for me the real game changer compared to all previous editions, and I think the point that the OP is complaining about.
So... Yeah. It was absolutely an evolution of the 3e design. First streamlining point buying into a single choice made at level 1, then lowering the maximum skill check value, then lowering it even further for Bounded Accuracy.
While there is an ancestry here, the effect of bounded accuracy and adv/dis are the game changers here, the other two points have nothing to do with the OP's problem.
Advantage was designed to support Bounded Accuracy while maintaining some measure of the old "I get +2 from being a catfolk, +1 from my magic cloak, +3 from my skill ranks, +2 from dex bonus, +4 because it's dark, and +12 because it's the last tuesday in June." modifier pyramids into a simple binary of benefit rather than a discussion of Bonus Typing and Stacking.
Not only did it considerably quicken the game (a brilliant design choice IMHO), it's also part of the game changers (compared to skills chosen at level 1 and "max bonus") because once more it contributes to what no other edition did, allowing untrained characters to regularly beat very skilled ones at skill checks (because modifiers, even stacking ones, could never compensate the differences of skill and abilities of previous editions where these were mostly unbounded - both the "proficiency bonus" and the ability modifiers went up arithmetically with level).
So, for me, the only way top prevent this has nothing to do with going back to the roots of the system, it has to do with compensating for bounded accuracy and adv/dis mechanics, both new to 5e.
I would hasard maybe getting proficiency and expertise slots based on INT, or maybe level or feats, so that characters who really want to specialise can get bonuses that are so differentiating that they cannot be beaten by normal folks and so that they can succeed at really high DCs (25+) with some regularity.
And I would also advise certainly not going back to modifiers, especially not negative ones that are almost never used in 5e and that are universally hated when they are negative.
