This is an ironclad solution, but it requires me to change the world a little too much. This story requires an enormous monster, which requires people to exist who can defeat that monster.

@MarcusYoder Fair enough; your question did not indicate that, but I realized it was kind of a risk as a suggestion. Unfortunately, it’s the only true fix.

@MarcusYoder that seems disputable. I don't know what the monster is, but one would assume an army of 10,000 6th level characters could take down pretty much anything.

@MarcusYoder remember that an "enormous" monster is only enormous compared to the ones that face it. A CR 13 monster would be considered undefeatable if you whole world was capped at level 7-8

Another option is that the spell True Resurrection does not exist in this world, even though other high-level spells do. The GM always has the option to add or remove any options he likes.

@MattThrower Actually, the way the math works in Pathfinder, a high-level character, to say nothing of a monster, may literally be immune to a 6th-level character and thus able to ignore arbitrarily large numbers of them.

@MarcusYoder: Nah. It'd just be considered army-worthy.

@Joshua 1000' field of rot; every minute you are in the region you take 1 point of damage and must make a DR 15 fortitude save or become fatigued. If you are already fatigued you become exhasted. If you are already exasted you become unconscious. Recently dead bodies (less than a year) who remain in the effect for more than 1 hour have their flesh gradually rot and become uncontrolled skeletons. Have that creature move to a city, the city becomes a necropolis. Without immunity to fatigue, your army is doomed...

@KRyan I tried to keep my question concise. Which turned out a little unfair to your answer. Sorry.

@Yakk I have to be careful not to pick a monster that can cast that.

@MarcusYoder It’s fine, I knew the risk I was taking with this answer. It remains a good answer for others with similar questions.

@marcus the point is that there are a myriad of effefts that make armies cry, but a small group of heros can defeat it, with modest CR on the creature.

@Yakk: Polymorph self is a low-enough level spell.

@Yakk. I got that. I was looking for creatures with CR in the mid 20s that are not COMPLETELY immune to mid level characters. I don't want the players to feel like there is nothing they can do against this thing, but I want it to be crystal clear that they cannot take it on alone. Your comment reminded me that certain monster abilities eliminate that possibility.

@MarcusYoder Unfortunately, Pathfinder is not a great system for that, and I really do think it will work better with PCs at 6th-8th-ish and the monster at CR 10-12-ish. That’s still a massive level gap without getting into some of the more problematic things at high levels. (Unfortunately, Pathfinder CRs are also wildly variable, so there are also CR 10-12 things that a 6th-8th-ish party could handle solo—and others nearly as bad as certain CR 18-20-ish monsters.) (This is not offered as an attempt to convince you to change your mind, just an explanation of why my answer is still here.)

Your best bet for CR 20+ encounter with creatures that are not immune to mid level characters is a mix of multiple creatures of less than 20 CR individually, (but add up to your desired CR) that semi-complement each other without being overwhelming to the party. A bit of a challenge, but by tweaking the encounter environment, the HD of the creatures, and their attack/escape strategies, it can be pulled off. Remember Tucker's kobolds! The concepts apply at all levels of characters and CR of monsters. (tuckerskobolds.com)