I like the idea of finding a fix for the runaway skill problem at higher levels, but I think your proposed solution shifts the problem to low level PCs instead.
With the Rule of 3, a 1st level PC that attempted to completely max out a skill could only hope for a +3 or +4 at best, vs. +0 for a completely unskilled PC. That differential just seems too small... it basically prevents a highly skilled low-level PC from doing anything an average commoner couldn't do, they just get to do it a bit more reliably. A rogue with Dex 18 who attempted to max out their Open Locks / Disable Device skill would have no chance of opening even an average lock until level 3-6, even taking 20 with masterwork tools.
You have a point, and I have noticed that myself. BUT... I figure that anything above DC 15 should be pretty difficult for low-level PCs - they're little better than commoners themselves until they get to L3ish. Also, I've reduced the DC for opening locks (since you mentioned that) to start at 10 for very simple. A very simple lock is something that a kid with a bobby pin could pop inside of a minute, so it makes little sense for it to be DC 20.
The Rule of 3 also doesn't really address the complexity issue at high levels, where each skill has an excessive number of modifiers. Kitty Joker's idea is kind of interesting in that it kills two birds with one stone. Ability scores already have plenty of uses beyond modifying skill checks (ability checks, combat bonuses, prerequisites, extra spells, etc.)
On its own, it doesn't, no. I'm working on that, too - this is part of a larger ruleset. All you have to do, really, is cut down the number of different bonuses that can add to skills. I reduced it to ability, circumstance, competence, enhancement, insight, morale, and racial. Luck bonuses are basically the same as circumstance, so that was easy to drop. Insight rarely, if ever, comes up, and racial is a limited bonus, so we're left with ability, circumstance, competence, enhancement, and morale. Of those, I'm seriously considering combining competence and enhancement, since they're basically the same thing; circumstance is a limited bonus (rarely more than +5), so between enhancement and morale, that's not a lot.
What do you think of this idea... instead of adding ability mods to skills or dividing everything by 3, just say the total bonus for any skill can ever exceed the key ability score for that skill. So for example, a PC with Cha 15 has a max Bluff skill bonus of +15 from all sources. This soft cap could be raised by increasing the key ability score by any means.
Hmm. Interesting. I see some loopholes/problems with it (does boosting the stat score via magic item increase the cap?), but it could work.