If you’re good on this, may I suggest making the mercenaries themselves memorable for something beyond being mercenaries? Perhaps they are eunuchs. Perhaps they serve a dragon and fight wars in order to bring treasure and information to their master. Perhaps their leader is enamored with humanity and is extraordinarily erudite; all the orcs emulate humans as best they can. Perhaps they are blinded in one eye (per D&D’s Gruumsh), and fight only in hand-to-hand combat. Name them, give the leader a memorable personality, and make them morally ambiguous.
How about, at the gate of their camp, a few neat racks of battle trophies and of the skulls of hard-to-kill creatures, and a sign with some variant of this old spiel and “For Hire” written in three major languages.
Dwarves. Seasoned dwarven fighters are pretty tough to beat, and having a lot of dead dwarves on the battlefield, and not too many orcs, should be an indicator. I also like the idea of the orcs having very nice well-kept armor, weapons, and equipment
You might sprinkle some half-orcs in there, too, if the game world allows it. Some half-orcs might very well be proud of their orcish blood, and think that orcs/half-orcs are the toughest, meanest race around, and should take advantage of their strengths.
Worse yet, orogs: half orc, half ogre. I don’t think they’re quite as bright as half-orcs, though.
Actually, I can see bloodlines being used as the basis for rank, with orc grunts, orog sargeants, and half-orcs as tacticians/officers. Throw in some ogres for “heavy artillery,” and you’ve got a pretty formidable force.
The PCs arrive in a new town, and all of the adventurer-work has already been done. The goblin tribes have been driven away, the children have been saved from the ogres, and the local necromancer has been slain. The orc mercenaries have saved the day, and for a princely sum. Not only have the orcs demonstrated their skill, they have earned a degree of admiration from the common folk.
Another idea: what if nobody realizes they’re orcs? Let them wear full expensive armor with frightening designs, mostly not speak, except their eloquent leader; break their orcosity on the players only once the players are convinced they’re dealing with badass humans.