I've been playing D&D for over 30 years now, and have played first 3.5E and now 4E for almost four years now.
One thing I've found is that "social" skills are Bluff, Intimidate & Diplomacy are usually too easy in game. A good Bluff check, and the formerly loyal guard with strict orders is letting the PCs into the castle... a good Intimidate check and the fanatical follower of the Evil Tyrant God is spilling the beans on his group's secret hideout.
I really think these things should be much more difficult.
Sorry but, IMHO, the loyal guard who has strict orders not to let anybody into the castle (under penalty of death) isn't going to suddenly forget his job because a PC rolls a good Bluff, Diplomacy or Intimidate check and defeats his Will defense or he fails his Will save or whatnot. I mean, if the king finds out, the guard may end up being beheaded and his family also executed. I would think that would put any sort of bluff/intimidate out of reach without magical persuasion.
Similarly, the fanatical follower of Evil God of Tyranny isn't going to give up the location of his secret hideout because a PC says "Boo" to him and rolls a 19 Intimidate check, modified up by X ranks in Intimidate and more through Aid Another. I would think the intimidation of betraying your god and spending an eternity being tortured for that betrayal is worth more than some PC talking to you sternly.
Using magical charm or domination spells is another story. I'm talking about just using the "social" skills.
How do people handle this situations?
Okay, first of all... this should never, ever happen. Imagine that you're approaching a guard post in real life (have you ever entered a military base?). You approach the check point. Normally, you flash your ID and you're let inside. Well, ID Cards and stuff don't typically exist during medieval times, but the premise is very much the same. So, things go something like this...
The Players approach the castle gates. There is a guard posted outside, and several posted on the wall looking down with crossbows.
PC's (to guard at gate): "Ho there! We've strict orders for you to allow us into the castle, straight from the Overlord himself!"
PC (to DM): "Can I roll a bluff check?"
DM (to Player): "No, not yet."
DM (to PC who asked to enter the castle, as the guard): "Huh? I donno what your talking about! We've been given strict orders by the Overlord to hold this castle and not let anyone in who don't come with his personal seal and writ."
PC (to DM): "What... we need the Overlords personal writ and seal to get inside?"
DM (to Player): "Yes. That's what the guard told you."
PC (to guard): "Uh... erm... the Overlord was too busy! He's given us strict orders to enter the castle immediately, and if you don't do it there will be trouble!"
DM (to Player): "Roll an intimidate check."
The intimidate check is successful.
DM (as the guard): "The guard suddenly takes on a look of concern, shifting uneasily. Then says, 'We can't let nobody in without his seal 'tis his own orders, I swear on the Evil God of Tyranny that it is true. I'll get the Captain.'
The guard then taps his sword on the castles stone wall making a loud clanging sound. The head of one of the guards with a crossbow peers down at him, and you hear him muttering, 'Eh? What? What do they want?!'
The guard from down below goes, 'Oi! Grish go get the captain! Some folk here claim the Overlord told 'em to come inside, but they don't have his seal and writ.'
There are murmurs coming from up above that you can't make out, and it appears as if one of the guards - not Grish - leaves to get the Captain."
The players shift uneasily in their seats, the DM grins.
DM (to Players): "Alright, one of the guards has gone off to get the captain. Are you guys going to sit around and wait for him to show up, or are you going to do something else?"
Players discuss it, and then decide they're going to wait.
DM (to all the PC's): "About twenty minutes pass in a long silence. The guard you've intimidated looks uncertain of all of this, mostly confused, but also perhaps fearful of what the Overlord will do to him for disobeying.
Finally, at last you hear commotion behind the gate. You hear the sounds of wood scraping against wood. Six armed guardsmen, swords drawn and ready with menacing glares all focused upon you appear as the door swings open.
You hear commotion from above. Looking up, you see a tall and imposing figure, a man with a well kept black beard streaked with gray and a long scar running down the length of his face. He is better dressed than the other guards, and you make the obvious assumption that this must be the captain.
Next to the captain are four more guards with crossbows drawn - all of them pointed in the direction of you guys."
This is where the DM grins broadly and chuckles, and the players begin to worry about the potential death of their characters.
DM (as the Guard Captain): "You lot had best have a very good reason for attempting to enter this castle. The Overlord has given me strict orders to not allow entry to anyone without his seal and writ. I am told you lack these things. Have I been told false?"
Players (to DM): "When do we get a chance to bluff?!"
DM (to Players): "You can begin bluffing now. You're going to have to convince the Guard Captain that you really were sent by the Overlord without the things he's requesting."
Player (to Guard Captain): "How dare you question us? We've been sent by the Overlord. He was too busy to give us these things that you want, and we have been given strict orders to be allowed entry!"
From this point forward, bluff checks are allowed. Most likely they will fail, and if so, the Guard Captain will order his men to attack. However, diplomacy could also be used in an attempt to seek a middle ground. Perhaps the players rethink their strategy. They attempt to persuade the Guard Captain to give them entry and to send a rider to the Overlord with a message to PROVE their claims. This buys them time.
However, no matter if or how they're successful, they'd be under heavy guard... but it gets them inside the Castle.
Other methods to increase their chances could have been used. For example, had they spent some time spying on the castle rather than riding up to it, they might have seen some of the Evil Overlords men displaying his writ and seal. They could have captured one such group and obtain that seal and writ for themselves, getting past the initial guard without too much trouble.
It's the job of the DM to create obstacles for the players. Anything that is considered an auto-win - regardless of what the rules state - is something that you have the ability to change and
SHOULD change.
When it comes to things such as diplomacy, NPC's always have the opportunity to avoid engaging in such matters with the PC's. They can avoid it by choosing to fight, refusing to engage the PC's, or remove themselves from the encounter. Sometimes the NPC simply can't give the PC's what they want, as is the case of the guard above. He didn't have the authority to allow the PC's in without a writ and seal, even after he was intimidated. So he did what anyone in that situation would do: they turned to someone else with the authority, in this case it was the guard captain.
If you desire a more robust social resolution system, I've found someone's blog which has converted the AsoIaF Intrigue System to D&D. I haven't used it, but it could be something you might find useful / helpful to you.
You can view that blog entry
here. If you are interested
here is the link to the AsoIaF Quick Start Rules (which includes the Intrigue System).
I hope this post has been helpful to you.