Honestly, have you ever heard of things like Swellow, Moltres, Scyther? They all outspeed and OHKO. Then you have a whole bunch of Fire-types - Moltres again, Arcanine, Houndoom, Blaziken (Speed Tie) and the Psychic types - Alakazam and Espeon leap to mind.
Sadly, nearly all of those that you listed are severely hampered by Stealth Rock.
Then, you have counters, in the loosest sense. Rhyperior can take 2 of Cross's CCs without fainting, Registeel can paralyze it for others, and even stuff like Gallade can revenge kill.
Paralyzing Heracross is a double-edged sword, as Heracross can simply use the Guts boost as a disgustingly powerful hit and run CB set.
It's not that powerful. Sure, it'll cause waves, but it won't overpower at all.
Let's run some calcs. I'll use the simple Adamant CB set.
Megahorn vs. 6 / 0 Jolly Swellow: 574 Atk vs 156 Def & 261 HP (120 Base Power): 237 - 279 (90.80% - 106.90%)
Swellow can't switch in on even resisted attacks.
Close Combat vs. 248 / 148 Bold Moltres: 574 Atk vs 288 Def & 383 HP (120 Base Power): 128 - 151 (33.42% - 39.43%)
Considering that Heracross outspeeds this Moltres, its an easy 2HKO with Stealth Rock.
Close Combat vs. 208 / 4 Jolly Scyther: 574 Atk vs 197 Def & 333 HP (120 Base Power): 93 - 110 (27.93% - 33.03%)
Baton Pass Scyther.
Close Combat vs. 252 / 252 Impish Arcanine w/ Intimidate: 382 Atk vs 284 Def & 384 HP (120 Base Power): 174 - 205 (45.31% - 53.39%)
Once again, Heracross can outspeed and 2HKO. Less bulky Arcanine will obviously take more damage.
Megahorn vs. 6 / 0 Timid Houndoom: 574 Atk vs 136 Def & 292 HP (120 Base Power): 543 - 640 (185.96% - 219.18%)
Not even sure why I did this calc.
Megahorn vs. 6 / 0 Adamant Blaziken: 574 Atk vs 176 Def & 302 HP (120 Base Power): 105 - 123 (34.77% - 40.73%)
4x resisted attack is denting Blaziken, hard. There is no speed tie, by the way, as Heracross is 5 points faster.
Close Combat vs. 6 / 0 Timid Alakazam: 574 Atk vs 126 Def & 252 HP (120 Base Power): 293 - 345 (116.27% - 136.90%)
Close Combat vs. 252 / 40 Timid Espeon: 574 Atk vs 166 Def & 334 HP (120 Base Power): 222 - 262 (66.47% - 78.44%)
Dual Screen Espeon.
Megahorn vs. 252 / 252 Impish Rhyperior: 574 Atk vs 394 Def & 434 HP (120 Base Power): 187 - 222 (43.09% - 51.15%)
Megahorn is really hurting it, so CC isn't even needed.
Close Combat vs. 252 / 252 Impish Rhyperior w/Solid Rock: 574 Atk vs 394 Def & 434 HP (120 Base Power): 280 - 333 (64.52% - 76.73%)
Several of these checks are relying on outspeeding Heracross after a kill...which sounds alot like Garchomp (something that is undeniably suspect, at the least).
Should Hera run the Adamant Scarf set, it is now outspeeding base all of the above threats (barring a scarf of their own) and doing roughly 2/3s of the damage listed above, which is still quite impressive. Out of the top 50 UUs, only 2 are ghosts (Mismagius and Spiritomb), and neither of them are too keen on switching into CB Megahorn, allowing Heracross to spam Close Combat relatively safely.
If and when a check comes in, it can simply switch out, then switch in later to repeat the process. Status isn't stopping it anytime soon, either, as it only boosts its attacks.