What did they think?

[Lalwendë]

The Bush and Blair alliance? Who's the evil one there?

It's Politics.

And different cultural values, and different expectations, and realism and all manner of things which drives nations to make alliances with other peoples making sometimes surprising bedmates. Who would have thought that the USA and USSR could be allies in WWII but they needed to be to rid the world of the Nazis. Who would have thought that the USA and China would ever be allies but they are now, seemingly to flood the world with merchandise (thus proving that its not just desperate circumstances which make for odd bedfellows).

The Rohirrim of course overcame their own innate prejudice against the Woses and ended up making an alliance with them; I don't doubt that the ordinary people of Rohan may have viewed the woodsmen as though they were 'dirty savages' judging by what's said when they meet up. But desperate times forge alliances, and from those alliances often comes greater understanding - looking on the optimistic, non-cynical side of matters... Perhaps as the Men of Umbar viewed their side as the 'just' side in the war, they overcame their own prejudices against Orcs in order to make an alliance?

As an aside, I would not let the UK off so lightly for their role in Africa.

[Boromir88]

I think Selmo hit the nail on the head...and as Tolkien talks about...in War indeed you have 'Orcs' on both sides:

For we are attempting to conquer Sauron with the Ring. And we shall (it seems) succeed.But the penalty is, as you will know, to breed new Saurons, and slowly turn men and elves into Orcs. Not that in real life things are so clear cut as in a story, and we started out with a great many Orcs on our side...~Letter 66 (regarding WW2)

[Kuruharan]

The orcs viewed themselves as courageous and indispensable at being sent as the front line of attack
-mormegil

I’m not so sure about that, but…

Men were a bit more intelligent and realized that they, the orcs, were being used as fodder to soften up the opposition and would rather be used for the more strategic and final blow offensive
-mormegil

…that is plausible.

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.Selmo

Hmmm…I don’t know how temporary it was. It seemed to be a permanent fixture of their terms of service.

They might believe that once the West was defeated, men would have the upper hand and get rid of, or lord it over, orcs.Selmo

…that is plausible.

I wonder how the orcs played into the theology of the Sauron (Morgoth) worshiping Men. I’m sure the Nazgul probably had some significance, but what about orcs?