There is always that. I am really considering that if the campaign continues for a long time the ending to the entire thing would be a fight with Asmodeus, God of Hell / King of the Devils. Then again there is no way to really get the stats for a character like that, let alone allow the PCs to gain enough power to face a true god.
Sure there is. Deities & Demigods has stats for
lots of gods. And then there's the Immortal's Handbook, though that was only released as a PDF. But I used the IH to run
two games with divine PCs all the way up the ladder until they were many times more powerful than the deities they'd started out worshiping as 1st-level mortals long ago. Of course, both the books mentioned are for 3.X rather than PF, but you could use them as baselines if nothing else.
Statting up a god is usually a lot of work, but if you have time and are thinking long-term anyway... there are ways to do it credibly.
So far we have had 1 session. The first half was a few small fights leading up eventually to the Mu Spore (taken from bestiary 2). It is CR 20, but was a rather worthy opponent. Even though nearly everyone had their full attack each round, the beast lasted about 10 rounds and took down the gunslinger to about ¼ hp. The problem I had with this was that a major part of its attack is to be able to grapple each person every time it hits. Because every character in the party has an item with freedom of movement on it, or had it cast, I was never able to execute this grapple.
FOM is to be expected at 20th, yes. Most people by then- even in a game that started at 1st and went all the way up- will have FOM items or some other way to keep it on constantly. It's too useful not to do that. The only way you'd really prevent that, as a GM, would be disallowing custom magic items and never giving them any that grant it. And not only is that vindictive and railroady, it's also pointless in the long run- because they can just buff instead by casting it, as you noted.
This gets to one of the top things people have trouble with at high levels: dealing with party powers in some manner other than just taking them away. Basically, it's a learning process of just accepting that you won't be able to use that type of attack against them; smart enemies will recognize the fact almost immediately and switch gears to something else (or better yet, use information-gathering spells/investigation before ever meeting the party to learn of their strengths and weaknesses in advance).
This is the main reason NPCs are more effective than by-the-book monsters at high level; NPCs are usually more adaptable and have more resources to bring to bear.
The next part of the session was a little bit of role-playing in order to find a Jabberwock (CR 23 also taken from bestiary 2). Part of the role-playing was finding out they would be facing a Jabberwock and a chance to prepare for the fight. This was definitely a mistake as doing so meant that they were able to take it down in about 3 rounds and taking very little damage themselves.
Another example of why Divination is one of the most powerful schools of magic- despite being so often overlooked. In my divine games, the PCs almost never acted without using every information-gathering resource they had, as many times as they could, to wring the cosmos for all the information it would give them on their enemies. We'd often spend two sessions just investigating, before ever getting into an actual combat.
This isn't everybody's idea of "fun," and certainly a couple of the players would get bored during sessions like this- but power-gamers love this sort of thing and invariably do it when given the opportunity. From your earlier descriptions it sounds like you have a party full of that type, so I'm guessing they had a grand time figuring out how to beat it, even before the actual combat.
Some advice from personal experience here: if you're decent at multitasking, you can take advantage of down-time like that, time spent on nothing but investigation, making preparations for future encounters. Players usually spend a few minutes castings spells or using skill checks to get answers from you the GM, and then tens of minutes arguing about the results and what to do about them. Those tens of minutes are when you can use the lull to do other stuff.
As far as the characters, each one is very well rounded. The Monk hit for 150 HP one round with his fury of blows attack.
And believe it or not, that's actually pretty low damage for a Full Attack from a 20th-level character focused on fighting. I've often seen serious tanks (Fighters, Barbarians, Paladins) dish out that much damage down around level 13, let alone 20. With high-level monsters, you want to avoid giving the tank/front-line-fighter the chance to use a Full Attack action whenever possible- stay mobile. If you let the tank Full Attack, you may as well be holding out your neck and saying "kill me."
He also has a very high touch AC and CMD. Other then SU or spells I’m not quite sure how to attack him.
That's the Monk's strength, yes. A 20th-level Monk should be
absurdly difficult to actually hit, or get in any sort of Combat Maneuver. Monks are primarily a defensive class, as James Jacobs himself has stated on multiple occasions. You have the right idea- don't try to attack him physically. Use magic first- then, if the enemies manage to get him helpless or restrained somehow, they can open up a can of whoop-ass at that point.
The Gunslinger is the easiest to hit, but the huge advantage for the particular class is that all attacks within about half the distance are counted as against the touch AC. Finally the Cleric is possibly the most powerful. Not only is his AC very high, he has multiple 9th level spells that are very difficult to fight against (Astral Projection, Gate, Miracle, and a few others).
To be expected, on both counts- Gunslinger should almost never miss at that level; the key there is she's a ranged attacker and can't easily deal with enemies that get up in her face. The Cleric was considered the most powerful class in 3.X with good reason- a buffed-up Cleric wading into melee could usually out-damage a single-classed Fighter or Paladin with ease, and be tougher to damage or take down to boot. Hence the term you might have seen floating around the Internet: CoDZilla (CoD stands for "Cleric or Druid"). The key with a Cleric is, they usually need lots of buffs to get that powerful- so lots of
Dispels will ruin their day. And then there's the nuclear option,
Disjunction, but that should be used sparingly if at all because it's a serious "ruin your day and possibly your character" effect.
I know I sound like I am complaining,
No, actually you don't.
You sound like exactly what your first post said you were, a guy who wanted to try something Cool and learned only after he started that he's in a little over his head. As I've related above, you already have the right idea on several points, so it seems to me you're off to an excellent start so far.
but I am genuinely enjoying it so far. I have just come to a point where there are few monsters left in the bestiary that will challenge them. The tentative plan for next time is to create from scratch 3 or 4 level 20 characters, and have them fight after a little role-playing. Maybe even for the competition of who gets to run a small city.
And the most important thing by far is- if you and the players are having fun, then You're Doing It Right.
You have already run into the fact, though, that monsters aren't as effective as NPCs at these levels. So going through the exercise of statting up new characters during session time should help- pay close attention to what the players say and do when they make them, you'll often hear tips for how to make such characters yourself. And then go make some. Once you've done it a few times, and seen what your players do with the rules, you'll start to notice certain combos and builds that Just Plain Work- and then you can use that knowledge to build such characters more quickly. This will cut down your prep time considerably.
Also, it is often the case that you won't
need complete stats for a high-level NPC, because (especially if they're enemies) they won't be around "on stage" very long in the game. You can therefore often leave some things undecided or blank, until the NPC shows up in game, and then you can "fill in the blank" on the fly with whatever seems to work at the time. This, too, can considerably cut down your prep-work. Many, many NPCs I used in my long-running Epic/Divine games were nothing more than names and a few jotted class-and-level notes on sheets of paper, on my side of the screen. And the players never knew.
Unfortunately it's very difficult to convey just how to get away with doing this; it's more art than science. My best advice is to try leaving a few small things (like low-level spells on an NPC spellcaster, for example) blank at first, and see how it works in play- then gradually try more and more things until you're comfortable doing it most of the time. Experience is definitely the best teacher.