Of course, there's a question that hasn't been asked: if we're at a level when most PCs can fly, should climbing remain a valid challenge at all? Or should it instead be assumed that a skilled PC can just succeed at anything but the toughest climbs?
Very true. My Paragon tier Dragonborn Fighter with Scion of Arkhosia for his Paragon Path had an overland flight speed of 12. I was good at climbing, but didn't really
need to be anymore. I could just fly up, and then put in a piton and drop a rope to the rest of the party.
If it really is the same wall, then that is indeed stupid. And probably bad DMing/bad adventure design.
However, if the wall that the PCs have to contend with is, indeed tougher, that's a rather different matter. Which brings us to...
Indeed. The key here is that most walls shouldn't be like that, and the PCs should be able to succeed even without a roll. By and large, climbing should just cease to be a problem at those higher levels. It's only when faced with a climb that is somehow tough (no equipment, a strange construction, extreme time pressures...) that they should have to roll.
But that's a feature, not a bug.
Exactly. If you always want mundane things to be a challenge, then end your campaigns in the Heroic tier. Paragon and Epic are meant to be played as if your characters are living legends. Heck, just look at the descriptions on some of those Epic Destinies! Undying Warrior? Demi-God? These characters are beyond being simply mortal, and should routinely be crushing entire armies under their boot...but a simple oiled rope should be able to stop them?!?!
I find myself wondering if maybe it's not enough for the math to simply escalate. Perhaps, as the game moves into a new tier, we actually need an entirely different set of resolution mechanics, to freshen things up? (Of course, I have no idea how that would be done, or what it would look like!)
That might not be a bad idea. After all, we have new mechanics introduced at those tiers anyway. New feats, new items, paragon paths, epic destinies, paragon multiclassing, losing powers for higher leveled versions, etc... Maybe we also need a different sort of skill check system too? Something like Passive Insight and Perception perhaps? This would allow trained characters, or those with stat/miscellaneous bonuses, to automatically succeed at some mundane challenges, but would still require rolling for especially difficult ones.
If the players want to make such tasks increasingly easy as they level I expect them to spend some resources on it, skill focus, appropriate magic items, etc.
In many cases they
do spend resources on it. A Fighter has 3 skill choices, one of which might go to Athletics if he wants to be good at climbing. He must also bump his STR score every level in order to remain good at it and keep up with the scaling. Yes, he was probably going to do that anyway since it's his primary stat, but that doesn't change the fact that it's a
resource.
Even without "spending resources", and just relying on natural level scaling, characters don't get as powerful as you seem to think. A Wizard with a starting 8 in STR is going to have a -1 to climb at level 1. He'll have difficulty even climbing a simple rope (I know, we had one in our party like that once...had to use a STR check to haul him up the wall with a rope around his waist, which was not very "heroic").
At level 21, he'll have a 10 in STR, and a +10 bonus due to the half-level increase. So now, this Wizard that has been adventuring for
years at this point, fighting alongside his companions and bringing nations to their knees, and is perhaps now preparing to create a dimensional gate to the Far Realm to fight the Mind Flayer scourge, can finally climb a rope pretty easily. Climbing up a rough cliff wall though? That's still moderately difficult and would be helped quite a bit by having some decent climbing gear.
How is this something that's utterly breaking the game? Sure, the Fighter can climb even sheer, smooth surfaces with ease, but that's his job! How many times have we seen the warrior in armor scaling the outside of the castle? Or climbing the cliff to surprise his enemies? Heck, how many times have you seen images of
real life free climbers doing unthinkable things with their bare hands? A 21st level Fighter is so much more than these real life examples, and should be able to accomplish those tasks with ease!