Comparing paladins to spellcasters isn't reasonable. They fill different roles in the party. Compare paladins to fighters and barbarians. Compare the monk to a ranger. I think they stack up fairly well at all levels.
I understand. Let us compare melee to melee. Paladins are roughly on the level of the fighter in core (tier 5). Lower than the Barbarian (tier 4) due to the barbarian's superiority at beating people up and taking their stuff.
Monk does not compare favorably to the ranger. Rangers get full BAB, more skill points, more skills, and better skills. That translates to better offense and out of combat utility. Rangers have worse defense, but as I have previously noted, defense is only good if you can make an impact.
And I have played 3.5 extensively with different groups in organized play and outside organized play with house rules and even without house rules at all levels, and I do mean literally all levels, inclusive, even epic, and I can say with certainty that there is acceptable parity between these classes and the roles they are expected to fill.
What a coincidence! So have I! I also hang out with people who play the game a lot and crunch numbers, and yet we have much different conclusions.
Monks serve as invaluable scouts for parties who are willing to wait.
Without search, disable device, open lock, or trapfinding, they leave much to be desired compared to the rogue. Springing traps to disarm them is a poor idea as some traps are alarms, and the whole point of scouting is to covertly obtain intelligence about obstacles ahead.
They are also nigh-indestructable at higher levels and capable of moving swiftly through the battlefield towards more fragile but deadly threats like spellcasters and neutralizing them with grapple, disarm, trip, and stun, once again without requiring dedicated spellcaster resources.
With all due respect, a high level monk is a joke when it comes to magekilling. If you doubt me, a demonstration can be arranged.
tl;dr Conjuration makes people with spell resistance very unhappy.
They can get to places other party members can't in a pinch with excellent physical skills or abundant step in a pinch, once again without requiring dedicated spellcaster resources.
One question springs to mind: how are you getting excellent physical skills while also being a scout? Monks get 4+Int mod skill points. Hide, Move Silently, Spot, and Listen are already four skills that you're scouting monk has. How does he fit in "excellent physical skills", which I take to mean Balance, Jump, Cllimb, Swim, and Tumble, without having a very high Int?
And what effect would that have on his other ability scores? Can't stun a mage without high Wis for that Stunning Fist save, and you can't hit him without either good Str or Dex.
Incidentally, if you're going to compare Monks to Rangers, an Horizon Walker can get Dimension Door with a CL of his character level (not half his level like that of the Monk) every 1d4 rounds at character level 11, one level before the Monk gets his.
Not that Dimension Door is a bad ability, it's a very good one. It's just not that good. Doesn't make up for not being able to stand up in melee or be a scout. Monks don't get much that synergies with it; they're kinda unfocused, with abilities that sound cool and are sometimes useful, but which don't work together as well as those of other classes. (Offhand, Barbarians.)
Paladins can tell you whether something is evil or not with a simple glance. No need to wave your arms about and murmur magical musings.
Alternatively, you could just have the Rogue pull a Sense Motive.
Higher level opponents having undetectable alignment? Well by that time paladins are getting spells like zone of truth and eventually discern lies.
What's the save on those abilities by the time you get them? I bet it's so high that the evil preist who casts Undetectable Alignment on himself will surely fail that will save. I'm sure it'll just burst through spell resistance as well, what with casting it at a CL of half the paladin's level.
They're immune to disease.
Everyone with a good fortitude save is. Moving on.
They have incredible saves.
Misleading. Paladins have good Fort and poor Will and Ref. They get Cha to saves... but that only makes the saves incredible if you have high Cha. Which means you have lower Str and Con. Which means you're not really stopping the hydra from rampaging across the town and killing your party members as effectively as you should be.
They are bastions of defense on the front lines who can dish it out when its on the line and heal in a pinch too.
In which case, you're decidedly inferior to a melee Cleric or Druid, which are melee classes that can dish it out, and take it even better than the paladin. Which would make your assertion that they work well with all classes incorrect.
And when atop their mounts they are more ferocious than any other mounted character due to all the incredible bonuses their mount gets.
Wouldn't a mounted druid be more effective since his animal companion is more powerful, he gets the same number of feats, and can have higher strength due to Wildshape, or at least allocating a lot to Strength?
Are there trade-offs for more direct damage routes like the fighter or barbarian? Sure. Whether those trade-offs are worth it depends on the campaign and how creative the DM is with encounters. If every monster is simply a mound of hit points waiting to be chiseled away, then take the fighter or barbarian. But if the DM likes to use interesting terrain, cunning foes, or encounters that don't involve monsters who just want to bash your head open, you might find the abilities of the paladin and monk are far more effective than the more straightforward tactics of the fighter or barbarian.
I could use an example. Would you kindly humor me?
Let's take a cunning enemy in difficult terrain. It's raining. You're in a city. There's an
Ice Devil reining havoc upon civilian crowds from atop a building. What does a Paladin or Monk contribute over a Barbarian when the level 13 party goes to stop it?
Edit: And since you mentioned flying threats in your edited post, I will note that many GMs allow a paladin to get a griffon or hippogriff fairly early if he wants it. And if he doesn't, there are plenty of ways to make a horse fly.
If you're using a griffon or hppogriff, you're not using your mount. One of your major points about how the paladin is worth it is the fact that they get an incredible mount... which is decidedly less incredible than you describe as the bonuses do not include flight.
As for making a horse fly, sure you can... with a
54,000 gp magical item.