1.) Getting to quasi-"invulnerable" range (AC 28-30) requires a lot of specific investment by the paladin. Giving up two-handed weapons/GWM in order to have a shield; giving up other fighting styles for Defense; giving up Smiting spells and other concentration spells for Shield of Faith; multiclassing to sorcerer or wizard for Shield spell; giving up Counterspell and AoOs in exchange for Shield (this makes you a worse tank--even Sentinel won't help you protect the party if you blew your reaction already on Shield); getting another PC to give up their concentration to Haste you.
Of course you must add in that putting magic items in the game also adds to the invulnerability.
2.) If you're letting the sorc Haste you, you just inherited new vulnerabilities along with the spell. If the Stone Giant hits the sorc with a thrown boulder, you lose your next turn. Haste creates risk and ties you more strongly to the party, which means more than ever that attacking the party is attacking the paladin. The paladin can't afford to just ignore the rest of the party.
True. The sorcerer has a good Con save. If he has warcaster, he has a good chance of making Concentration checks.
3.) The paladin is relying on buff spells, so he's vulnerable to delays. If the fight is going sour, the enemy can potentially break contact and open the range for a few minutes while the buffs wear off. I've found that players get very nervous about leaving active hostiles in the neighborhood--they're not equipped to simply ignore the enemy right back, they will pursue. Which leads to...
The PCs usually have superior ranged attacks. Choosing to go range may make the paladin have to sit tight, then the superior ranged strikers get to start to hammer.
4.) The paladin is still vulnerable to things that bypass AC, like falling damage from getting shoved into a spiked pit, or hitting a ghast's poison cloud. Aura of Protection helps somewhat, but it mostly just compensates for non-proficiency. It's only Wisdom and Charisma saves where a paladin feels semi-invulnerable. On Dex and Con saves he feels strong-ish but he still hates having to make repeated saves. See above #1 for opportunity cost: if he's got Shield of Faith up he doesn't have Bless to protect his saves. Combine #3 and #4 to encourage the paladin to get ahead of the party and chase the monsters into an area where this weakness can be exploited.
Aura of Protection helps a ton. It makes them less vulnerable than anyone but a high level monk. Cleric or bard usually casts bless. So paladin ends up with both.
5.) The paladin's AC-based defenses are mostly magical in nature. In an anti-magic field, or after a Dispel Magic, he's exactly as durable as a Defense-specialized Champion Fighter in the same plate armor + shield, and perhaps less durable than the equivalent barbearian or rogue.
Sure, throwing an antimagic field or hitting the paladin with a dispel magic is highly effective. Though at the moment I think he can still smite in an antimagic field and he still gets all his other nifty stuff.
6.) And of course there's the infamous Grapple/Prone combo. It's often not worthwhile against characters with low AC because you can just kill them, but the harder it is for you to hit someone, the more actions it's worth spending degrading their defenses. Remember that the paladin only gets one attempt per round to break the grapple, and he can be grappled by more than one opponent at a time.
The grapple/prone tactic. Very effective if it works. A vengeance paladin can misty step out of it. A group of creatures using their actions to grapple/prone someone often ends up getting hammered by the other party members.
You always have the option of going after other PCs, but the above ideas illustrate how you can threaten the paladin personally, in ways that are about as threatening to the paladin as they are to the other PCs.
Paladin is one of the toughest classes in the game. Paladin/warlock or paladin/sorcerer adds to that sickness. It's a very powerful class with fewer weaknesses than other classes. They even get a more powerful animal companion horse than the a low level ranger beast companion. That is really odd to me.