Were the southern and eastern kings bent to Sauron's will?

Question

We know Sauron bent most the orcs of the 3rd age to his will, but were the men of Khand, Rhun and Harad bent to his will as well or simply bribed?

Answer 1

This depends on what you mean by "bent to his will".

We read in Of the Rings of Power and the Third Age:

In the east and south well nigh all Men were under his dominion, and they grew strong in those days and built many towns and walls of stone, and they were numerous and fierce in war and aimed with iron. To them Sauron was both king and god; and they feared him exceedingly, for he surrounded his abode with fire.

This is the clearest statement that I am aware of regarding Sauron's domination of these peoples in post-LotR writings, but - of course - "under his dominion" could have many meanings - magical, political, coercion, bribery (presumably with Rings), etc are all valid interpretations.

If we go back to the Lay of Leithian (History of Middle-earth 3) we read:

Men called him Thû, and as a god
in after days beneath his rod
bewildered bowed to him, and made
his ghastly temples in the shade.
Not yet by men enthralled adored,
now was he Morgoth's mightiest lord...

This is a pre-LotR writing (easily identified by it's use of "Thû" rather than "Sauron") so the geographical expansion and tales of the Second and Third Ages didn't yet exist when it was written, but it's use of words such as "bewildered" and "enthralled" certainly suggests some form of magical domination.

Answer 2

Morgoth had previously bent them all to his will, and Sauron was building off of that.

Prior to the main events of The Silmarillion, Morgoth had subjugated the tribes of Men in the East to his will. Morgoth hadn't been around there for a while by the time Sauron came, and it thus took Sauron a good ninety years to pick up the pieces, but one imagines it would have been even more without Morgoth having done the leg work.

But until [S.A.] 1600 he [Sauron] was still using the disguise of beneficent friend, and often journeyed at will in Eriador with few attendants, and so could not risk any rumour that he was gathering armies. At this time he perforce neglected the East (where Morgoth’s ancient power had been) and though his emissaries were busy among the multiplying tribes of eastern Men, he dared not permit any of them to come within sight of the Númenóreans, or of Western Men.
...Thus it was that though, as soon as his disguise was pierced and he was recognized as an enemy, he exerted all his time and strength to gathering and training armies, it took some ninety years before he felt ready to open war. And he misjudged this, as we see in his final defeat, when the great host of Minastir from Númenor landed in Middle-earth. His gathering of armies had not been unopposed, and his success had been much less than his hope. But this is a matter spoken of in notes on “The Five Wizards”. He had powerful enemies behind his back, the East, and in the Southern lands to which he had not yet given sufficient thought.
_{The Nature of Middle-earth - "Note on the Delay of Gil-galad and the Númenóreans"}

Sauron's work in the East was also opposed by the two Blue Wizards, who the Valar had sent to disrupt him, and to help guide the Men who were starting to break free of Morgoth's reign during Morgoth's long absence.

The 'other two' came much earlier, at the same time probably as Glorfindel, when matters became very dangerous in the Second Age. Glorfindel was sent to aid Elrond and was (though not yet said) pre-eminent in the war in Eriador. But the other two Istari were sent for a different purpose. Morinehtar and Romestamo. Darkness-slayer and East-helper. Their task was to circumvent Sauron: to bring help to the few tribes of Men that had rebelled from Melkor-worship, to stir up rebellion ... and after his first fall to search out his hiding (in which they failed) and to cause [?dissension and disarray] among the dark East ... They must have had very great influence on the history of the Second Age and Third Age in weakening and disarraying the forces of East ... who would both in the Second Age and Third Age otherwise have ... outnumbered the West.
_{The Peoples of Middle-earth - "The Five Wizards"}

Both of the above texts come from a bundle that Christopher Tolkien refers to as "Last Writings", which was written in 1972-1973, the final year of Tolkien's life.