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.