Out of the ones listed, Tyris is currently the best, followed by Orkhin, especially since the names of the Orcs are slightly different in Heroes of Might and Magic V. You're going after "real" Orcish names, but here it's not quite right.
It's like with Drago – you could really come up with a lot of names from the Biblical-Catholic concept, but how does that fit into the concept of Erathia? Let's give the knight the name Judas, or Isaac, Mark, etc.
And they complained that the female names of the Mages should be similar to Ora and Nura. But the fact that they could have other names inspired by the East is not allowed.
Vidomina was in Heroes of Might and Magic III, as far as I remember.