What an unusual topic.
I think I'd rule that the paladin could teleport away, leaving the NPC and glue behind. Otherwise you could stop someone from teleporting, dimension dooring, or plane shifting with nothing more than a tanglefoot bag, and that sits wrong with me. A tanglefoot bag is a heck of a lot cheaper and more readily available than
Dimensional Anchor. And where does it end? If the glue is effective, what about a small character and
Evard's Black Tentacles? There's as much chance of that halfling breaking away from those tentacles as there is of the paladin getting away from the NPC without Universal Solvent. Does
Evard's Black Tentacles block teleportation spells? What if a druid uses
Stone Shape to have a boulder reach out and pull a sorcerer back against it, then shapes the stone around his torso? That sorcerer is stuck to that rock but good. Can he
dimension door away?
Speaking of incident, incidentally, I as a player become extremely annoyed with DMs who railroad me into traveling with annoying characters. It isn't fun to be annoyed, and the only reasoning for it I can come up with is that such DMs are amused by my annoyance. Not the kind of DM I want to be playing under.
As a DM, I have introduced annoying characters in the past. Usually they are characters who are fun for me to role-play, but can quickly get on the players' nerves. But I never force them to travel with these individuals, and most of them are dropped like a bad habit.