Okay so KoD already gave a really good answer, but I just wanted to say a few more things about them (more to do with competitive prediction).
Salamence
The problem with Salamence is that you have no clue what set it's running until it makes a move. And even then you're not sure if it's mixed or physical. The issue with this is that there are therefore no safe switch ins to Salamence, as it can be packing Fire Blast and Earthquake, which would mess up any Ferrothorn (that isn't in the rain) or Heatran (that isn't holding Air Balloon) switch in if your opponent predicts correctly. Blissey is also not available as an option as her defence is negligible, and Salamence might just pull an Outrage because it's only resisted by Steel (in Gen V; Blissey might be Fairy in Gen VI, who knows). Additionally, it could be either banded or scarfed, and that's pretty hard to tell unless, say, it never sets up Dragon Dance, or your opponent switches when it uses a move that one of your Pokemon is resistant/ immune to. If it does set up D-Dance, it's usually holding Lum Berry, so it can snap out of confusion.
I guess the only "easy" thing about facing a Salamence is being able to tell its ability right off the bat, as Intimidate will activate immediately, and Moxie will only activate once its fainted something.
Lucario
Again, you have no idea what set its running until it makes a move. However, with Lucario it usually runs either purely physical or purely special, since it has access to both Swords Dance and Nasty Plot. The issue with running a special set is it only has one priority move, Vacuum Wave. A physical set could see it have Bullet Punch, which has no immunity problems from Ghost types, or Extremespeed for more power.
The real problem with countering Lucario is if it's physical or special. If it's physical, Gliscor is the best counter, and if it's special, Tentacruel is the best counter. The good thing about Lucario is that it's usually holding Life Orb or Expert Belt (or, let's hope not, Focus Sash) to make full use of its stat boosting moves, so if you have Mach Punch on Infernape, then you can OHKO Lucario since it has poor defences. Sadly, Infernape is the only Pokemon with Mach Punch that outspeeds Lucario.
Scizor
Scizor doesn't really pose the moveset question like the other two pose, but it does pose the problem of Super Power, which will mess Magnezone up, since so many of them have Metal Pull instead of Sturdy to trap Scizor. Scizor is pretty much standard counter to Terrakion, Tyranitar, and (less commonly) sash Aerodactyl, since it packs Technician Bullet Punch as well a Swords Dance. However, once again, it's difficult to tell if its running Scarf, Band, Leftovers or Life Orb until it makes a move.
The other major threat Scizor poses is Pursuit, as Espeon, Alakazam, Celebi and Latios, which are all capable of running HP Fire to OHKO Scizor, might have better options for their move sets and not be able to deal with Scizor without it.
I guess the best Scizor counter is really Heatran, unless the Scizor is scarfed and packing Super Power, but most people wouldn't let Scizor deal with Heatran if it's at full health. Or Gliscor, since there's nothing Scizor can really do it it, or indeed Landorus-T with Intimidate.
