Don't allow your players to say things like "I use Diplomacy". Make them say a specific action, "I try to convince the King that sending troops would increase his popularity with the people". Basically, you don't want the Skill to come before the action. You want the desired action to drive what Skill is used.
Agreed. But I take it further. You are required to narrate specifically what you do. So a player who said, "I try to convince the King that sending troops would increase his popularity with the people.", would be told, "Ok, so do that. What exactly do you say?" The player is then expected to at least say something like, "Your majesty, sending the troops would increase your popularity with the people."
At that point now, a diplomacy check is called for, and is modified by the following:
a) How valued is the PC to the king, so that the king would desire to please the PC?
b) How much risk is the PC asking the king to perform?
c) How much authority does the PC have relative to the king, so that the king would be inclined to listen to this opinion?
d) How well aimed is the appeal? That is, is this the sort of king who would care what the people think of him? Or does this king only care about his purse?
Those factors together taken together will produce a DC. If the PC is disliked and of low station, and the king risks much by sending troops, and cares little for popular opinion, then the DC might be set quite high - say a DC 28. On the other hand, if the PC is a trusted advisor the king counts as a friend, the king risks little by sending troops, and deeply cares about popular opinion, then the DC might be set quite low - say a mere DC 5.
At this point we roll the dice to determine how the king receives the suggestion. And note, despite the range of difficulties involved, nothing is set in stone. If the PC is a slave in the king's court but happens to have a +20 bonus to diplomacy, his appeal is interpreted to be so eloquently presented and so charismatic - far beyond how any player could have worded it - that the king almost can't help but be moved. Whereas, if the PC is a low charisma man of a stumbling tongue and an unintentional confrontational manner, the PC's is interpreted as having made the otherwise reasonable request in the most insulting and grating way possible. But notice, the content of the message being conveyed is already set by the player in his proposition. The dice only tells us the style and skill with which the content is presented. In this way, we have the best of both worlds (at least IMO). We have both real association between the actions of the player and the imagined world, AND we also as much as is possible, allow a player to play and receive the consequences of a charisma that might be quite different than his own.
And note, that when you play in this way, sometimes interesting and unexpected things happen. First, note we are taking into account the suitability of the appeal. A player can figure out whether or not to appeal to the king's purse or his vanity or his tenderheartedness - or he may just stumble into the 'right' sort of reasoning. We can also take this as a repeated challenge, were each failure might make the king less likely to cooperate (he gets more and more annoyed, which ups the DC), but where retries are allowed when the content - the appeal - is changed. Thus, this can be made into an extended challenge involving much role-play at the table. Second, the players can organically or even inadvertently change approaches. I've had players who want to make a diplomatic appeal, stumble into something that sounds more like a threat, "Your majesty. You must send your troops or the people will have no choice but to revolt against your rule." Suddenly the PC might find himself making an intimidate check or a bluff check. And of course, by design or by accident this can be a much worse or much better approach.
The more you know about the NPC, the more intricate the challenge can be. The important point though is the social challenge here has a structure, but it's a conversational structure - not a wholly abstract structure artificially welded to the situation where the player's choices are largely motivated by game mechanics and not the details of the situation.