The Orcs are notoriously hard to pin down
Orc tribes are nomadic and drive great herds of giant gazelles (which are also used as mounts) from fertile area to fertile area to avoid overgrazing. They move fast and have no permanent settlements. When close to human territory, young males like to raid, even at the risk of death - it is kind of a rite of passage, and the older males don't mind, since it leaves more young females for them.
When the Khan sends out troops for retribution or extermination, the tribes just move away, having received early warning from their lookouts. Their gazelles are faster than horses, and the Orcs themselves are capable of running long distances at a good pace, while horses require frequent rest. Hunting orcs is a very frustrating experience. The grasslands are so vast that any organised attempt at conquest is impossible - orc tribes can easily slip through gaps or weak points in any front line.
Compounding the problem is that Orcs breed a lot and mature quickly (say, 8 years from birth to maturity), hence replacing losses quickly. Typically, numbers are kept down through warfare between tribes, trying to steal gazelles or young females. There is, however, a maximum feasible size of tribes of about 500. Once a tribe reaches this size, it tends to split into two, often peacefully, at other times as a result of attempted coups against the ruling chief. Ar any rate, if the Khan begins to kill off a lot of Orcs, the tribes are perfectly able to keep the peace between each other and concentrate on killing humans instead. Losing two or three Orcs for every human enemy killed is seen as acceptable, since it takes far longer to resupply human armies through breeding. Long-term campaigns against Orcs have been tried in the past, but have been lost due to attrition. It is better in the long term to simply defend settlements against raids and accept whatever losses are incurred.
Some Orcs choose to serve the Khan as mercenaries, even against their own kind, but tribal Orcs look down on these mercenary Orcs, who tend to mainly be outcast for some crime or another. Serving an inferior species is very low status.