Was it not decided, oh fifteen or twenty pages ago, that a Pokemon not having counters was not a viable argument for banning? You point out Cresselia as being a sort of counter but say that it "will take hefty damage" but that is true of switching into almost every sweeper.
Also, as much as I disagree with Mence going to Uber, I wish people would see the intrinsic flaw with simply comparing him to Dragonite as justification; which, is happening on both sides of the table.
I think for a pokemon with such offensive calibre as Salamence would be at least considered for Uber if it had NO counters...I mean for something with lower Atk/Spa it would not matter as much, but when a pokemon has such high offensive stats, decent typing, extremely poweful STABs and complimentary SE moves makes there almost no direct counter. And when we say 'hefty damage', we mean 50%+, allowing for 2HKOs including the switch. If you look at something like Infernape, you can easily switch to Tentacruel with little or no fear, don't bring up but the SD Set rapes tentacruel [tentarape?], because that set is rarely used.
Honestly, I rarely have a problem with Salamence on the OU ladder. It is incredibly easy to scare out, regardless of the set, and it truly poses less of a threat to my (most of) teams than other common sweepers like Scizor or Heatran or Lucario. Well, maybe not Heatran. This is not because I designed them with Salamence in mind but because he is incredibly easy to revenge kill. So what if he takes out one member of my team. If I revenge KO it, I just took out one member of his team, probably one more integral to his team. Any Pokemon is a problem once it starts boosting up, which is why they made priority moves in the first place. Also, if he just took something out with Outrage, guess what move he's gonna use next.
The pokemon you listed are ALL checks/revenge killers. None of them can come into 2 out of 4 of his moves, and those 2 moves are likely to be chosen on the switch, as to not be -2 SpA or locked into Outrage, but you can't really tell can you? Also Jolly Life Orb ExtremeSpeed form 252 Atk Lucario against 0 HP / 0 Def Salamence 319 Atk vs 196 Def & 331 HP (80 Base Power): 122 - 144 (36.86% - 43.50%)....Choice item users can't really be considered checks/counters, as in they can, but anything that HAS to lock itself onto a move just to take down a Pokemon gives your opponent a free turn to set up, im not saying they don't count, but lets look at other options. I mean locking yourself into Ice Punch/Ice Beam is like saying hey, now set up with something else!! Remember Salamence can switch out too, and although kind of irrelevant, many teams use a rapid spinner soley so there Salamence does not take SR damage. But anyway, 252 Atk Scizor @ Life Orb does 394 Atk vs 196 Def & 331 HP (60 Base Power): 169 - 199 (51.06% - 60.12%), with Choice Band and SR its a OHKO, but then you are giving your opponent a free switch and a free turn to do whatever they want.