What did they think?

[Selmo]

In our own world, nations have always alied themselves to evil men when it suits their political and economic ends.
Think of the UK and USA allied to Stalin's Soviet Union in WWII, the UK working with white supremisists in South Africa, the USA arming any brutal dictator who was anti-communist, the UK honouring the communist dictator of Romania with a knighthood, just a few example from the twentieth century.

Mankind has always been able to set aside it's principles for gain. Why should the men of Middle Earth be any different?

Sauron's and Saruman's men would feel themselves to be superior to orcs and would probably find working with them distasteful but they would accept what they would see as a temporary situation that would benifit them in the end. They might believe that once the West was defeated, men would have the upper hand and get rid of, or lord it over, orcs.
.