Bauglir said:
Even if the soldier was 'Derek the Truthful, he who never lies', still the situation IMO should not be resolved in his favour without ever rolling a dice. The diplomat has many routes to go down to make a halfway convincing story, and all his charm to make it stick. Perhaps the 'enemy soldiers' were some third party attempting to plant evidence to start a war? Perhaps Derek has turned to evil? (a harder bluff but not impossible) or perhaps (dum dum DUM) this isn't Derek at all, but someone posing as Derek in an attempt to start a war?
Important NPCs are not automatons manipulated entirely by random numbers. You forget the fact that, in any situation, people are predisposed to believe certain things and favor certain patterns of behavior: Trying to convince somebody of something he already believes to be true is very, very trivial, and when somebody is telling you something that you already suspect is true, while somebody else is telling you something which contradicts that, you're already innately predisposed to believe the former, even if he did. All this can matter far more than how skilled a negotiator or debater either party is. Skills CAN be made entirely irrelevant under the right circumstances: When modifiers became stacked so high that the task has become impossible, a failure can be ruled on any attempt without even rolling: If even a 20 cannot grant you success, there's no reason to roll it at all, and the situation described definitely warranted heavy modifiers: Predisposition, reliable confirming witnesses with credible evidence, the works.
Furthermore, while the diplomat DOES have many routes to go down, none of the matters if he DOES NOT USE THEM. Perhaps he could have explored those options: On the other hand, perhaps he didn't feel it was worth the risk of being labelled as a snake, and chose not to push the matter too hard. As you said yourself, a hard, but not impossible bluff: Let us not forget that a failed bluff has highly negative consequences to one's credibility. Even if success was possible, it's quite possible that success in the short run would be detrimental to the diplomat's career in the long run, and a failed attempt disastrous.
Remember that, with all the combat tactics in the world, the combatter is still slave to his attack bonus (+/- a small circumstance bonus - flanking etc) and abilities. A mage cannot bypass a dragon's armour & DR just by coming up with a really nice way to stab it with his non-magical dagger, while the fighter is having trouble denting it. In the same sense I would not allow a fighter to outperform a charisma based character in their field of expertise, just by coming up with a good story, particularly if the character in question is unlikely to have been smart enough to come up with that story in the first place.
You, sir, are clearly thinking in very hide-bound, one-track ways. A combatant is NOT necessarily a slave to his attack bonus: Attack bonus only matters if you, personally, are directly attacking an opponent: Plenty of tactics can be executed without this: For instance, the lobbing of grenade-like weapons makes your attack bonus far less important: To simply strike him at all requires merely a ranged touch, and even failing that, you'll still nail him in the splash radius. What effects occur depend on the specifics of what you're throwing. Other tactics are completely unrelated to attack bonus at all: Dropping the ceiling on your opponent is highly effective, can be done at even low levels in the right conditions, and being smashed under many tons of rock hurts. A lot. A mage with a nonmagical dagger cannot bypass a dragon's DR merely by thinking of how to stab it, but there's no reason why the mage has to do this: Plenty of other options may exist that you might not even have considered, due to your preference for thinking in the box. Combat is a complex affair which is more than simply combatants trading blows until one or the other is dead.
D&D is a complex game where, as in life, the larger numbers don't necessarily always win.