An interesting plot twist might be:
Six months go by, and then the NPC returns triumphant, wearing armor made from the hide of that blue dragon. When asked about it, he tells the tale of how he used a cool head and a silver tongue to convince the dragon to let him live, and then killed the beast by dropping a giant boulder on its head while it slept. Now a paladin himself, he wears the dragon's hide as a reminder to always be calm, and always be brave, even in the face of impossible odds.
He's not angry at the paladin who handed him over to the dragon--to the contrary, he's grateful. "If you hadn't sent me on my first quest, I never could have become the hero that I am today." And then the paladin in blue armor rides off into the sunset on his summoned steed. The players will occasionally hear news and rumors of this "blue knight" as they travel the realm, often showing up to fix the things that they broke and to clean up the messes that they made, until their own paladin shows him up by completing an epic quest of his own.
I think that having the paladin "fall" would be a bit too harsh, but letting him get away with it completely would be a bit too lenient. So this example wouldn't "punish" the paladin directly, and wouldn't strip him of any of his abilities, but wouldn't let him glamorize or ignore it either.