This is complex.

Machiavelli's writing indicates that he was fiercely loyal to the Republic of Florence. This made him somewhat inconvenient to the Medici, who were at the time trying to dismantle the republic and declare themselves Grand Dukes (recall that at the time, the Republic of Florence ruled over an area roughly corresponding to the entire Italian Region of Tuscany). I do not know of any evidence indicating that he was actively applying for a job elsewhere by writing The Prince, I always thought it reads like a "You Need Me, Take Me Back," message to Lorenzo de Medici.

That being said said, the administration of the large republics at the time; Venice, Genoa and Florence, normally only appointed positions of responsibility to citizens of their own nobility. On the other hand, the Princely States, such as Milan, Mantua, Parma and Urbino, appointed people based on skill, not nationality. You make the analogy of a democratically elected minister applying for a job at another government, and yes, in that case it might seem odd. But the case here is much different; unless there is a violent uprising, political appointments are made by a single person: The ruler; a Prince, and that is to whom ministers are accountable to, not the people. The most famous example? When Duke Lodovico needed someone to head the construction of the fortifications around Milan as well as redesign the city's canals, he hired the best engineer in Italy at the time: Leonardo da Vinci, a Tuscan (Yes, Milan had canals. Proper canals, not the three mosquito infested cesspools the city has now, you can read more about them and da Vinci in D. Arasse's biography of him, but I digress). A more typical example from later in the same century: Baldassare Castiglione was born to a family in the minor nobility in the Duchy of Mantua. He first served in the administration of the Duke of Mantua, but later found better pay in employment with the Duke of Urbino, who soon made him his ambassador to the Papal Court. In Rome, he had a sort of spiritual awakening after his wife's death, and some seven years later, he took a job as the Papal representative in the court of Madrid, in Spain. The life of Baldassare Castiglione is very interesting, however I can't find a proper text in English to suggest to you. What will probably be in your local library is The Four lawgivers: Savonarola, Machiavelli, Castiglione, Aretino by R. Roeder. The mods will probably complain that it's outdated. However, I think it's a good starting point.

The practice of appointing outsiders to political positions has a precedent in the way the Italian cities were run since the communal era. Many cities (usually smaller ones) selected a Podestà, or chief executive, who was a leading citizen of another city, for the simple reason that they could be expected to be free from conflicts of interests. As the Italian cities were eventually absorbed in the half-dozen or so Italian states of the renaissance, these individuals were replaced by appointees decided by the suzerain (be it the Republic of Venice appointing a Podestà to the city of Vicenza, or the Duke of Milan appointing a Podestà in Pavia). However, the idea that a person could hold public office because of skill continued to thrive. (if you'd like to learn more about this part of Italian history, I would suggest Lombard Communes: A History of the Republics of North Italy by W. F. T. Butler. Yes it's also outdated, but it's still a good starting point).

The practice is not uniquely Italian. Sometimes, even rulers of small states became key administrators of larger ones: Alessandro Farnese, Duke of Parma, was the governor of the Spanish Netherlands in the late 16th century, and commanded infantry that was to disembark in England, carried by the Spanish Armada. As late as the 18th century, you can find characters like General Von Steuben, who was a Prussian officer looking for employ with the Franch army, and eventually found his way to the United States, where he was employed in the American Revolution.

Military matters, of course, are unique, in the sense that as early as the 13th-14th centuries, the Italian cities were employing generals based on the amount of men loyal to them and their skill in battle, regardless of their provenience. Flipping through J. J. Norwich's A History of Venice, some wars were even won by buying out their opponent's mercenaries. In military matters, defection was indeed a big issue, however, I don't know of any record where changing allegiance in state administration caused more problems than a senior manager changing companies today.

I haven't answered your question though! Forgive me for going into so much detail. I'll answer your question very briefly here.

• What kind of background, duties, and compensation did they have? Normally they would be members of the Minor Nobility; people who would have to work for a living, but still be well educated, probably either in Florence or Padua. Their duties would depend on the individual structure of each state and the ability of individual rulers, but for our purposes we can assume they were more or less analogous to modern governments, using the term more or less very generously. What was their compensation? Blast it, I have no idea. Down-vote me if you must.

• How could they be trusted with state policy and administration if they might defect to a higher paying city-state? Money, dear boy. Also, most policy secrets were decided by the sovereign and shared in its entirety only with his family members. This is only a real threat for a Prince who is not prudent, or a republic, where the administration knows everything. Which is why the Republics only hired their own (again, check out J. J. Norwich's A History of Venice)

• Were they the main source of political theory essays like The Prince? The Prince was influential. Castiglione's Book of the Courtier was also pretty influential, and worth reading to know the kind of person that these "Politicians for Hire" aspired to be, although it does deal with rather banal topics.