Yes, they stack like the rule you cite says, if the specific class says they do. This is an example of exception-based design - the general rule is "only the one class counts" but then the specific rules in the other classes can say "but I do."
Not all prestige classes are alike so you should carefully read their Spellcasting benefit. In this case, Arcane Trickster says "I stack."
But classes that do not say that phrase, like Wizard and Sorcerer, do not stack. In your second example, Loremaster's spellcasting is worded like Arcane Trickster (as if she had gained a level in a spellcasting class she belonged to...), and you would need to decide whether you want it to stack onto your 5th level wizard spellcasting or your completely separate 3rd level sorcerer spellcasting. Assuming the former, you'd cast your spells from wizard slots at level 8 and your ones from your sorcerer slots at level 3.
It's kinda obvious why this is, the core idea behind prestige class design is "continue what you were doing, down a slightly weirder path" and therefore completely penalizing a spellcaster by e.g. halving their spellcaster abilities would be undesirable (even at that, many don't add a spellcasting level at every level and have one or two "penalty" levels.
Prestige Classes are just like any other Classes, except where specific rule says something else.
From OGL content*:
Prestige classes offer a new form of multiclassing. Unlike the basic classes, characters must meet Requirements before they can take their first level of a prestige class. The rules for level advancement apply to this system, meaning the first step of advancement is always choosing a class. If a character does not meet the Requirements for a prestige class before that first step, that character cannot take the first level of that prestige class. Taking a prestige class does not incur the experience point penalties normally associated with multiclassing.
Emphasis mine. So if Paladin takes a levels if PrC, he is multiclassing all right.
Now, your player is wrong. Paladin can take any PrC he meets requirements for. The only issue is - he cannot ever take a level of Paladin again, unless PrC says he can. If prestige class has a rule that says that character can get levels of Paladin later, then she can, because specific beats general.
Example of such class (courtesy of Charlie) is Knight of the Chalice (Complete Warrior, p. 53):
Multiclass Note: A paladin who becomes a knight of the Chalice may continue advancing as a paladin.
So this class is an explicit exception. Some classes in Defenders of the Faith are exceptions, too. Probably few more scattered across sourcebooks. And that's all to it.
* Note that part about no XP penalty never made it to 3.5 DMG. It was in 3.5 OGL SRD, in 3.0 DMG and in 3.5 Complete Warrior. And 3.5 FAQ but, surprisingly, not errata. And bit different wording in each place. In this answer, I took wording from SRD, because that's where OP got Paladin class from, so this makes most sense to me.
Best Answer
Your question boils down to two ingredients: Do prestige classes work like normal multiclassing, and does D&D 5e still have a level limit of 20?
Do prestige classes work like normal multiclassing? Yes:
Does D&D 5e still have a level limit of 20? Yes.
The prestige class rules offered in the playtest material in Unearthed Arcana do not include any change to the base game's level limit, which is level 20.
As a side note, the first prestige class we've seen (the Rune Scribe) offers 5 levels to multiclass into, not 4. It bears repeating that experience with mechanically unrelated games can be misleading and should generally be ignored when looking at how D&D 5e works.