Here is an example of optimizing AC. It has nothing to do with cheating and everything to do with just spending gold in the most efficient manner.
The OP never disparaged 'optimizing' as 'cheating'.
He just said his players don't like that play-style. I don't think your wall of crunch will change that.
I think Dennis just summed it up pretty well when he said that higher level play does demand more from the players. Maybe my gaming compadres just aren't willing to be paranoid enough to survive above level 10, but that's OK because we had a blast getting there!
This is the main point I think.
Look, if they are having trouble with APL+1 CR, they just aren't even remotely in the ball-park.But just because the game publishes Class Levels until 20 doesn't mean you have to play there.
Having your 'end game' around 12th level (or whatever) is just fine.
You can develop a new style of game at the end, most encounters not dealing with 'top end' opponents (however you define that, in your case seemingly lower than what is expected), and more with mass quantities of 'mooks'. Develop role playing as the 'powerful heroes' of the area. Etc.
There most definitely is a change in the expected play style from low levels to high levels, as well as in relative balance of class options, etc. Just becuase Paizo makes their high end game work a certain way, doesn't mean you have to play that game, and you don't need to feel bad about that fact, any more than you do because you don't like playing Warhammer or My Little Pony. But if you don't like playing My Little Pony, trying to play will be an excercise in frustration... So do stuff you like doing!
Rocket tag was the rule of the day in 3.5. PF hasn't change enough from that.
At higher levels, whoever goes first in a straight out fight (no worries about diplomacy, injuring the innocent, and the like), the side that wins initiative usually wins the encounter. And at the higher level, characters need to be better than average (possibly better than even above average).
I never played enough of AD&D to remember if that was the case as well, but I suspect the older D&Ds were like that as well.
As someone who played the older DnD games (Original Red Box, 1E AD&D, and 2E AD&D) quite a bit (we had actually 'mostly quit' because we were done with college by the time 3E came out), I do not recall any situation in which AC was even half as much of an issue at high levels as it is in 3E - or that winning initiative would guarantee a win/loss in combat.
Not disparaging 3E or Pathfinder (enjoying Pathfinder currently and not playing 2E so you have my ultimate choice there in my chosen actions), just pointing out that AC vs Attack was definitely different in older editions.
I've been doing this for a long, long time. Now, we're currently playing a mish-mash of Pathfinder and 3.5e, but the 'problems' are really the same for both.
However, short answer: yes, high-level play is for experts, or, at a minimum, experienced players - at least if you want to make a long-term game out of it.
--
Now for the long answer.
It's kind of like, say, Indy 500 racing or rock climbing. Anyone can jump in their car and stomp on the gas, but if the average Joe were to try to compete in a professional auto race, they're pretty darn likely to not only crash but probably take half the field with them.
High-level play is kind of like that.
When we decided back in 2006 we wanted to run an epic campaign, we didn't roll up a half-dozen 30th-level characters and start wiping out great wyrms and gibbering orbs and the like. I can remember doing that once in '03 soon after the ELH handbook came out, and while the battle was crazy, it wasn't anything that would turn into a long-term game.
Instead, we started at 6th-level and went up about a level a week, gradually easing into it; it took something like 3-4 months to hit 20th level. This was necessary not only for the players, but for me to figure out how to run this stuff - and even at that time, none of us were novices.
Now, just about 6 years later, some people have crazy-optimized characters, some people don't, and there's some that are in-between. My job is to put challenges in the game that play to their strengths and weaknesses while (a) not breaking the versimilitude of the game world and (b) not being cheese for the sake of cheese.
So, sure, some things they run into (note I'm not saying battles, there's a lot of non-combat stuff going on here) are easy, some are hard, and some I have no freakin' clue how they're going to solve it - but I don't worry about it.
Does it work? Hell yeah. Do we have fun? Yep, pretty much all the time. But what it takes, in my opinion, is a few core elements:
1. A plot or purpose. There has to be not only a reason why the characters are so powerful, but something for them to do. I can't begin to imagine trying to run a crazy epic level sandbox campaign.
2. Don't roll up high-level characters unless you're going for a one-shot game. If you want to have characters that are meaningful, actually play through from low-levels to high. You've got a lot more hard choices to make when you have to actually play those one and two level dips that the min-maxers are fond of.
3. Include something other than combat. All fight all the time makes Jack a dull boy, and it's never more true than at levels above 20. But those skills and abilities are good for things other than carving through bad guys like butter. So they've got friends who need help from time to time, and legacy magic items they're unlocking, and mysteries that need to be solved, all in addition to saving the world eight ways from Sunday. And they've only got 8 months or so to do it.
4. A group that wants to actually play the game. Even at low levels, a poor (or contrary) player or, even worse, a poor GM can ruin the game. This is exacerbated as levels increase. Note that I'm not talking char-op here, I'm talking about someone with an axe to grind, for example someone who thinks that high-level play is stupid and wants to "prove" it, or someone who likes to argue for arguement's sake, or someone who is determined to find and exploit every broken combination they can find. At our table, we want to play the game - if a combination is obviously broken (and when you're using 3.5e rules, but even with Pathfinder, you'll find them sooner or later), then we avoid it, use it in a way that makes sense, or do something else sensible for the sake of the game.
I won't deny it, it's a lot of work. But really - does anyone expect high-level play to be easy? Even low-level play isn't cake - gone are the days when you can tell a newbie "okay, you're the fighter" and they really don't have to know a darn thing - there are no simple classes to play any more between skills and feats and spells and class abilities and the like.
On the other hand, I am very much looking forward to when Paizo finally reveals that they've been working on mythic material, finishing up my current campaign, and starting a new one. And once again, we'll start at low levels and work our way up the ladder.