I see it as a way to reinforce personality with mechanics, something D&D needs more of (all editions). There's three ways to handle these sorts of things:
Absolute fiat:"I'm not bothering with mechanics, the Duke doesn't care, and that's that."
Let the dice fall where they may:"Well, my notes say the Duke is a man of iron resolve, but hey, you rolled a 52, so he crumbles to his knees and bawls like a little girl, I guess."
Mechanics:"You may succeed in scaring the Duke, but that won't make him help you the way you want."
I don't read the sample skill challenge as saying "The duke is magically immune to intimidation". I see it was saying "If he's intimidated, he won't do what you need him to do." For example, instead of sending aid, he might say, "You're right. Those monsters are too tough. We're packing up and fleeing south. See ya!" or "Well, you guys really are butch. Here's the certificate of ennoblement. This is your dukedom now, I'm outta here. The army's loyal to me, so they're leaving too, but, hey, I'm sure you can bully the peasants into forming a regiment quick enough. Bye!"
It's also worth noting that it's not written as "One intimidate and you lose." Presumably, playing this out, the first intimidate attempt will result in the DM dropping a serious hint that's the wrong way to go. If the players keep pushing the wrong buttons, well, sucks to be them.
It's much like any other kind of decision tree in a game. "If they go down the right corridor, they will trigger the 10d6 fireball trap". This is 'fair' if there's some way to detect/guess this is about to happen; it's pure railroading if there's nothing but dumb luck to guide the players.
I see it playing like this:
Duke:"Why should I give you aid in this quest?"
PC:"It's like this, Duke. Either you give us the Staff Of Plotdevice, or we take it. Either way, we get it, but one way, your castle stays standing and your guards stay living. How 'bout it?"
DM:The Duke's attitude hardens visibly. "Perhaps you have the power, perhaps you don't. You might consider that it is possible the Staff is better protected against theft than you think. I recommend you consider your next words very carefully."
If the PCs keep threatening, they will force the issue to a head, there will be a big fight, and they'll find the staff is warded to explode if anyone but the Duke touches it.
The alternative tends to be a one-skill-fits-all solution. If any social challenge can be solved with Intimidate, that's all anyone will have -- as I suspect it will have in-combat uses Diplomacy will not.
It is also worth noting that, in the Real World TM, men and women of power are often willing to die -- or let their people die -- before admitting weakness or failure. One reason peace negotiations drag out is that the leaders, on both sides, want a way to look like they've won even when they've lost. I can easily see a Duke being willing to let his kingdom burn, or even fight to the death against a superior foe, before simply surrendering.