The way I see it, it is all about putting pressure on your opponent.
Think of it this way: Every action in battle has a cost. This cost is measured in the amount of damage dealt, healed, stored via stat-ups, or prevented. You want to maximize the cost of every action your opponent takes.
Calling out your attacks removes two very important elements in your favor: prediction and surprise. Therefore, maximizing the cost of an opponent's action is key.
This means, first and foremost, to lay down Stealth Rock. Then bring a Ghost to block Rapid Spin.
Sandstorm is more often than not a double-edged sword here.
The cost for your opponent to switch to an immunity on your attack is 0. Stealth Rock makes that cost anywhere between 3-50%, usually hitting 12. The weakness of Spikes and Toxic Spikes is that flying types and leviators and immune to them, and thus they still can have a switch-in cost of 0 on Earthquake or whatever other moves they're immune to.
Stealth Rock means that the switching option always has a cost. It may be minimal, such as Claydol, Steelix, or Flygon switching in on Thunderbolt, but its there. SR really hurts the "switch flying types in on Earthquake" option.
The next idea is to use strategies that are predictable, but hard to stop. The first thing that comes to my mind are Bulky Sub-punchers. Tyranitar, Hariyama, Poliwrath, Kangaskhan, Dragonite, Dusknoir, and Breloom are pokemon that even if you know are subbing, you may not be able to break their Subs. Then it doesn't really matter if they know you'll Focus Punch, the worst that could happen is they'll switch in a Ghost. Since you set SR down, the cost of that action is 12% instead of 0.
Knock Off is another effective move for this. Even if they know Knock Off is coming, all that means is they can either try to KO your pokemon, or they have to choose which pokemon will lose their item. Such a large pressure can lead to mistakes.
Sucker Punch is interesting here. On the one hand it seems useless because your opponent can just stat-up in your face. On the other hand, knowing this can net you Leftovers HP, and if your opponent switches it is generally indictative that particular pokemon doesn't have stat-ups.
U-Turn combines some attack power with unpredictability since they won't know who you'll switch to. Unfortunately, a lot of things resist it.
Whirlwind and Roar are effective for the opposite reason as Subpunching: They are entirely random. Your opponent is basically hazarding a guess that you'll WW or Roar in the wrong pokemon. Thus, they'll either attack even if it isn't effective, or they'll switch hoping that a different pokemon gets blown in. Once again SR is crucial here, although Spikes and Toxic Spikes don't hurt any in this case.
So as a summation, a team which employs these tactics is probably going to have the best chance of sucess. I'd go with:
Swampert Surf/Earthquake/Stealth Rock/Ice Beam @ Lefties
Skarmory Drill Peck/Roost/Spikes/Whirlwind @ Shed Skin
Hariyama Substitue/Focus Punch/Knock Off/Whirlwind @ Lefties
Vaporeon Ice Beam/Aqua Ring/Baton Pass/Roar @ Leftovers
Dugtrio Earthquake/Aerial Ace/Stone Edge/Pursuit @ Choice Band
Dusknoir Substitute/Focus Punch/Shadow Sneak/Will-O-Wisp @ Lefties
Rapid Spin blocker, a trapper, a load of bulky pokemon, and lots of Phazers means even with prediction, you have a lot of difficult strategies to beat. Taunt Aerodactyl is probably the worst thing that could happen to this team, but it isn't as if he's going to stay in on Pert or Vaporeon often, or switch into a Substituting Hari or Dusknoir.