Ferghis -
The skill system I'm working on seems to have the same effect as what you described above.
Here's the link:
http://www.obsidianportal.com/campaign/p-p-rpg/wikis/skills
I've introduced the Too Easy mechanic: if an action is too easy for a character, he automatically succeeds. It's reinforced by the GM's difficulty roll: the GM chooses the difficulty of what a character is trying to do, and adds that to his d20 roll. The player has to beat this roll. Either the player or the GM can choose to take a result of 10, speeding up an automatic success.
Where you've named the skill levels, I have a more continuous progression (using skill points):
Untrained - 0 skill points
Trained - 1 skill point
Expert - 2 to 5 skill points
Master - 6 to 10 skill points
Epic - 11+ skill points
The "disadvantage" at making a higher level skill check is included in the Difficulty (
http://www.obsidianportal.com/campaign/p-p-rpg/wikis/rolls); the higher the difficulty, the higher you have to roll.
And when you attempt something that's too difficult for you, you'll have to roll a number higher than what's on your die.
For example, you're Trained in Deciphering. You have a +1 from your skill point, and a +2 from your intelligence. You can roll a maximum of 23 on a d20. But you're attempting a Master skill level, at +10. In my system, the GM can take 10 for a Difficulty Class of 20, or try to roll for a higher DC. If the GM takes 10, the player needs to roll 18, 19, or 20 on his roll (15% odds). If the GM rolls, the player needs to roll 8 higher than the GM (since he has +3, adding 8 will equal 11, or one greater than the GM's +10). The player has 50/50 chances of rolling higher than the DM. Odds of rolling 8 higher, though, also work out to about 15%.
Should skills reflect what you need experience for, as well as what you must study for? Well, it sure beats role-playing those lengthy exams.
Should life-or-death skills follow the same system (like attacking)? Well, why can't anything be life-or-death? You're about to get smashed by a giant, unless you can Jump-Skill your way across a chasm. You're a hostage in a brutal kingdom - better hope your Smithing is up to snuff (when they demand you work for them). Why can't attacking (I call it Fight) be less-than-lethal? Fencing with the prince? Use Attack for a snowball fight. You could use Attack for a game of billiards, curling, or bowling too.
My current system is dividing stealth into two skills: Sneaking and Larceny. I find that it helps to look at a skill from a class-perspective: would different classes be interested in different parts of this skill? In Thievery's case, I say yes. Divide it up.
Regarding the Olympic Track and Field team: I wouldn't call that trained and untrained. Being in shape means you have a good strength score, not that you have Athletics training. Plus, the dude who's in good shape (but doesn't have any skill points) still has a 5% chance to jump over the 12' high-jump bar. 1 in 20. Even though the trained people have better odds.
But think about this: it's those cheesy '80s movies where the main-character jumps over a wall (trying to save his girlfriend), lands in a 100 meter dash, and beats the competition. He rolled well. Or used what I call a Hero Point. Either way, it's better for the story for him to win, than to be the boring, untrained guy.