Man, am I glad to see this thread! It hits on THE problem that my group and I have been struggling with ever since we finished the RttTEE about two years ago.
Here are some thoughts I have had, in no particular order.
Start PCs at 1st level, but give them 5th level hit points. That’s all they ever get, then, unless they take feats (Toughness), raise their CON, etc. I think that this would open up the range of encounters for characters and the DM would not be so beholden to EL or CR. You wouldn’t have to worry about wiping out the low level party, an Ancient Red Dragon would really be horrific, but it could still be placed in the bullpen of monsters available to fight, really pushing the characters to use their wits to overcome it.
Cap character advancement at around 6th or 7th level, when classes get most of their good perks. PCs would not advance beyond that, though you might use something like the Epic level concept of still allowing feat selection as characters progress. You could also make a tweak to the spell casting rules to allow for finding, learning, and casting the odd high-level spell, though at great risk (can you say, Spell Burn??)
You could slow down progression using a different XP chart (like the one in the Wilderlands campaign, that more closely mimics 1E/2E advancement). This solution seems inelegant, though, especially if used alone.
I have always wondered why skill DC increases with CR while skill points increase too. I go up a level, I increase my ranks in certain skills. But the DC goes up by level, too, until you have a DC/skill rank arms race. Having been raised on both 1E and 2E, I still cringe when the rogue calls out, “I got a 34 on my Search for traps roll.” That’s just too high. Why not keep the Search DC for a secret door at, say, 20, and have slow down the skill rank progression? If you wanted to keep the mechanic of increasing ranks in certain skills, it should be retained only for character development purposes (I ran into Gord, and he showed me a thing or two about disabling poison needle traps). The bonuses would remain low, though.
The DND Basic Game has an interesting approach to this problem, I think. The DCs remain pretty static, but so do the skill ranks. All the rank/bonuses are given at character creation. Elves get bonuses in Search, etc. Humans get a +2 to any single skill. Rogues, the masters of skills, get a +4 bonus to everything. Etc. You could raise numbers through feats, increased ability scores.
Actually, the above is the same for AC. My BAB goes up, my opponent’s AC goes up. Why is that necessary? I ran some numbers back in 2E. I took what I considered the most common monsters PCs would encounter at 1st, 3rd, 9th, 12th, etc. levels and tried to figure the chances that a fighter, thief, cleric, and MU would have to hit at each level. The percentage remained pretty much the same. So again, why the numbers race? If I get a +15 to hit at 15th level, and the monster’s AC is up to 30, that gives me a 30% chance to hit. If I’m first level with a +1 and the monster’s AC is 16, that gives me a 30% chance to hit. Why this illusion of progress? (Maybe a similar study would be interesting for 3.5E.)
Although, I agree that leveling up is important and players need rewards of some kind. Maybe a reward in Status or Reputation, a role playing reward rather than a mechanical, numerical reward?
What we’ve been struggling with is keeping mid-level play, which we agree is the most interesting and challenging and most fun to DM, yet still having a system that allows character growth, customization, and rewards for the players. Gee, that seems pretty simple…?