Political games require both excellent record keeping and a willingness to let players have excessive impact by comparison to normal gaming styles.
Taking my own prior experiences, the best working political campaigns were in L5R and Pendragon... both games where I've made extensive use of record sheets in various levels of detail.
The details needed don't include the combat capabilities of the NPC's most of the time. They do require tracking what secrets they have, what their resistance is to PC manipulations.
It also helps to make a map of the major players.
Further, it's important to distinguish a Court game from a Rulers game... they are very different in how you scope things out.
For a court game, the secrets are very important. Everyone collects dirt on everyone else. So everyone should have some dirt to be collected. And then it helps to have a grip on who likes, hates, or is sleeping with whom. And, as history shows, often, gender was no barrier to that last one, nor was hatred.
For a Rulership game, the kind of game where one or more PC's are rulers in their own right, the secrets are less important, but the resources in terms of troops, allies, and enemies are more so.
In either case, knowing who wants what and has what else to offer for it is important.
Political games are where a good information storage mode is vital... you can very quickly wind up with more NPC's than you can remember. But you don't have to remember; you can instead just make certain you can find it when you need it.
Likewise, it's vital to be consistent in who has what opinion about any particular other important NPC. Which is where the cross-reference table is wonderful:
\begin{array}{l c c c c}
& & \rlap{\text{About}} \\
\text{Who} & \text{Edmund} & \text{Franz} & \text{Corwin} & \text{Ld. Dunny}\\ \hline
\text{Edmund} & - & +5 & +3 & -5\\
\text{Franz} & +1 & - & -1 & +1\\
\text{Corwin} & +5 & +6 & - & +6\\
\text{Lord Dunny} & -1 & +1 & -5 & -\\
\end{array}
You can see that Dunny really dislikes corwin, but Corwin likes everyone. (That's why Dunny is unhappy with him... he thinks him an annoying suckup.)
Such a table is particularly useful for court games.
Likewise, if you number or letter their secrets, you can record their dirty secrets on a second grid showing who knows which ones for whom.
Also, keep in mind that allies need not be friendly... Just needing or wanting the same thing(s).
Further, depending upon the game system and style of play and GMing, the amount of prep needed can vary widely. In a strongly narrativist game, such as Blood & Honor, you start with blank map and relationship grids, and fill in as established by the group in play. In a GURPS game, a strongly simulationist system, it's far more likely to have the map populated, and the grid at start filled in, and let players modify from there. Either way, being able to find what you need to know is the most useful skill.
Each character should have a page of notes, as well... starting off, pretty slim. As the game progresses, note down favors done for or by them, and manipulations, alliances, and backstabs.
Don't forget that, in the absence of PC interaction, all relationships are subject to change as well. Provide a means for doing so "off camera." This could be as simple as GM Fiat ("I think it's time for Dunny to put Corwin out to the front lines...") or as convoluted as making rolls on their loyalty scores to each other, to see if there's a chance of raising or lowering the other's score...
But the single-most important element of a political game is that nothing survives contact with PC's unchanged. Any political action by a PC should have an effect. Not always a good one, and not always a direct one. Other parties who know what they did may react to it. THe person manipulated should have a reaction whether they succeed or fail... even if that reaction isn't evident to the players immediately. Failed blackmail becomes a secret. Failed or successful sexual liaisons become secrets. Revealed secrets become scandals.
So, why do it?
Because in a political game, a lot of it is pure roleplay. A lot more is making the efforts to get where you need to be. It's not all about the convincing. A lot of it is etting up plots and strokes that happen outside the scope.
In fact, in my own political games, the politics are more scenario-generation than scenario themselves. The nastiness of courtly politics leads to flared tempers, rage, and pinning murders on others in order to get them out of your own way. Rulership games involve marshaling your troops, fighting your wars when they happen, and dealing with threats outside of court.
If you can find copies, Birthright for AD&D 2E and the stand-alone Reign or Houses of the Blooded all have great advice on the political game.
Best Answer
Consider having the characters designed so that there is some meaningful reason for them to be the ones selected.
I remember one campaign I played (Planescape) in where some red dragon asked us first-level scrubs to go find her precious stolen dragon egg. My response to that was "You must not want it back very much!"
Contrast another campaign (Eberron), where one of the PCs was of the dragonmarked noble house, and the rest of us were retainers or otherwise friendly/bound to him. He gets sent not because he's "high level" (metagame concern) but because he's an important guy, and we get sent because we're his posse. That's a lot better story.
In other words, if these organizations would hire "professional agents" - why are they not generating characters that are professional agents? Or are in that nation's military? Et cetera? The whole "let people generate anything they want and then it's the GM's job to somehow shoehorn them into the party and the campaign" approach is old and busted; don't do it. See this previous question on forming parties for relevant advice.
Of course suitability doesn't have to be "best for the job," it can mean "disposable," "the only volunteers," "some power bloc wants them to go," etc. In the Pathfinder Society, the organized play society for Pathfinder, all PCs have to pick a faction that is then part of the motivating force (and that works behind the scenes to get its agents included in certain missions...).
At a bare minimum, if this has to be a "hire off the street" kind of thing, have them try to make sure that they are at least objectively hireable. I remember one spacefaring campaign where a player's new character couldn't explain any reason why our space freighter crew should hire him. In fact, he was pretty militant about it - we were looking for reasons to bring him on, since he was a PC... "So, what do you do?" "Things... That need doing." "Uh, do you have any specific skills we'd find useful?" "I have many... Skills." After about 15 minutes of that we took off and left his dumb ass on the planet. (We actually bounced the player from the group too, as being a muffinhead like that was a common character trait of his.)