Call me a bit narrow-minded, but I really think any lead should have some way to play against Deoxys-S. I don't see how this works against Deo-S, unless Payback gets boosted just by moving second(in which case I eat my words).
It does, while there's no reason why you can't just use Payback once and start spamming Rapid Spin, since any hazard would just get removed anyway.
As for the Tentacruel lead, I'd consider testing an offensive lead, something like (EDIT: Actually just use mine, it's plain better, HA):
Tentacruel @ Focus Sash / Lum Berry / Life Orb
Ability: Liquid Ooze
EVs: 40 HP / 252 SpA / 216 Spe
Nature: Timid
-Hydro Pump
-Ice Beam
-Rapid Spin
-Toxic Spikes
Hydro Pump 2HKOs Deoxys-S, and you can always just Rapid Spin away the hazards it sets up anyway. It also handily 2HKOs Darkrai, so if you use Lum Berry, you're getting a good hit at him, I guess (If you use Lum Berry). Ice Beam OHKOs Rayquaza the majority of the time (LO can be used if you want to guarantee it). As for leads like Groudon and Dialga, if you're using Focus Sash, you're getting up 2 cute layers of Toxic Spikes on them guaranteed, unless they use Thunder Wave and you get fully paralysed twice in a row, lol. You can always save a 1HP Tentacruel to absorb Toxic Spikes later. This set isn't really outclassed by Starmie, since you can get hazards up, as well as being able to remove Toxic Spikes without having to use Rapid Spin. Item choice: Focus Sash to get in two layers against bulkier leads, or do just survive hits in general, while Lum Berry lets you get a hit in on Darkrai (or get a layer in), while LO makes sure you OHKO Ray with Ice Beam.
So, rehash on the top leads:
Deoxys-S: Hydro Pump 2HKOs, while Rapid Spin removes hazards easily
Groudon: Set up two layers of Toxic Spikes, and use Rapid Spin to remove SR if they set it up.
Darkrai: Bail if you don't have Lum, if you do, set up Toxic Spikes (1 layer)
Shaymin-S: Depends on how many times you get flinched, but Tentacruel can afford to get flinched once and OHKO with Ice Beam. Seed Flare does 51.13% - 60.13%, you easily live. On the topic of Shaymin-S you can always switch into SubSeeders and watch them kill themselves.
Deoxys-A: Lose. Extremespeed 2HKOs easily, although you can always just set up a layer of Toxic Spikes and then switch out.
Kyogre: Set up a layer of Toxic Spikes to see what set it's running. If it's Scarfed, switch out (or let Tentacruel die and then remove their revenge killer with Wobb, or Duggy if they're using Thunder). If it's a bulky variant, set up another layer of Toxic Spikes.
Dialga: Set up two layers of Toxic Spikes
Mew: Lose, although you can just pump and then spin away rocks as they U-turn out.
Giratina-O: MASSIVE LOSE. BAIL BAIL BAIL. (Or you can set up one layer and disappear, hehehe)
Forretress: Hydro Pump it and spin away any hazards they set up.