{snip}
Now it's true that p 58 also says that "The DM calls for an ability check when a character or monster attempts an action (other than an attack) that has a chance of failure. When the outcome is uncertain, the dice determine the results." But I would take it as obvious that the GM is meant to make that decision havng regard to the text I already quoted, as well as to what will make for satisfying play.
So the GM might decide (say) that it is impossible to influence a zombie or skeleton via threats, because they are mindless undead which have no heed to their own physical integrity. Or the GM might decide that an otyugh is not amenable to influence via tact or social graces, because it's an otyugh. But nothing there suggests to me that the GM should decide that an ordinary human being can't be influenced because the GM thinks it would make for a better story if that doesn't happen. Or because the GM thinks it would make more sense for the NPC not to influenced.
Three things.
First, I don't think I said that the DM had to decide the NPC in this case couldn't be persuaded not to have the PCs executed. I think my position has been pretty consistent that the DM could decide that, and has rules support to do so. Whether it's good or bad DMing is probably a matter of taste.
Second, the rules you quoted strongly imply the possibility that the outcome might not be uncertain. The judgment on that is left to the DM. Do you think it doesn't make sense that a Mad Tyrant might not be in a mental place to listen to reason after being insulted then attacked in his chambers?
Third, I think it's possible the DM has allowed the Mad Tyrant to be placated somewhat--he didn't have the other PCs arrested, after all, after what the OP described as (probably paraphrasing) "excellent die rolls and good roleplay."