"Before the rise of the horde two headed ogres were extremely rare. They were larger and more intelligent than other ogres and could even wield magic. At the the time of the First War Cho'gall was the first known ogre magi for generations, although others later surfaced"
See, Cho'Gall was the first known Ogre Magi for generations, so for around 100 pre-dark portal, which is where Kil'Jaeden begun influencing the orcs, there wouldn't be very many Ogre Magi around at the time, especially since the ABSOLUTE maximum age for Ogre Magi are 180, and they are venerable at a age of 120, and counted as old when they're 65...
And I can imagine an Ogre generation being 20 years, and "for generations" would be around 100 years, probably more...
But let's take the mentioned Ogre Magi;
Cho'Gall - Well, as mentioned he was the first known Ogre Magi, so he's the Magi Senior, and leader of the Twilights Hammer Clan, which became more of a doomsday cult under his leadership. Oh, and he was also the right hand of Gul'Dan... Every mothers dream, aren't he?
Blackheart: Well... Nobody know very much about this guy, but he was a member of the Shadow Council, and helped Ner'Zhul and Teron... So he seems pretty Horde-oriented, so I don't think was ever in the National Ogre Party.
Dentarg - Another one who helped Ner'Zhul, but this guy was just very devoted to him, so he seems to be a steady supporter of the Horde Party too.
Mogor - Leads the Laughing Skull clan, which implies that he isn't that old, since clan leaders seems to get challenged when they get too old, so... He probably wouldn't have been born a hundred years pre-portal
Soo... I don't really think you can use the Ogre Magi
