The absolute best cleaner in the game. Absolute best. Nothing stops Deoxys-A.
Superpower and Shadow Ball OHKO stuff like crazy. Shadow Ball should be your basic move, because it hits so much of the Uber metagame super effective, and Superpower hits just about everything that resists Shadow Ball super effective, as well as having massive power (120) for stuff like Kyogre that takes neutral to both. ExtremeSpeed can OHKO other Deoxys-A you might encounter, as well as allowing you to finish off a wounded Rayquaza before it can ExtremeSpeed you. Rock Slide can go on there somewhere if you're afraid of Ho-Oh and want to try for a flinch against Lugia, as well as hitting Rayquaza super effective. Ice Beam 2HKOs Groudon and OHKOes Rayquaza, which is very useful. Defensive Groudon can sometimes take two Psycho Boosts thanks to the Special Attack drop as well as the 90% accuracy (unless you invest a few Special Attack EVs, but why do that if there's a better option available?), and survives 2 Superpowers (you need to roll absolute max damage both times to 2HKO max HP Groudon, and some Groudon have Defense EVs). Ice Beam, on the other hand, will always 2HKO Groudon. Use Fire Punch with your own Groudon and Thunder with your own Kyogre to kill Skarmory, Forretress, and Metagross (especially Metagross, as Pursuit OHKOes you if you switch out).
Special sweeper. Deoxys-A can actually deal huge damage with +1 Special Attack from Petaya - you'll generally want to make sure to make your HP divisible by 4 so that the Petaya will activate on the third Substitute, thus allowing you to withstand Tyranitar's Sand Stream for a few turns, but HP not divisible by 4 can let you scout for misses with the extra Substitute. Superpower is for the chance to OHKO Blissey (especially with how few Blissey even have any Defense EVs), and it definitely does enough to Blissey if she tries to switch into you (since you can attack from behind your Substitute).
Because the Choice Band is far more common and seen as more powerful, Deoxys-A is always assumed to be Choice Banded. There are a few things that can stop this Deoxys-A, but because they'll be acting on the assumption that you are Choice Banded first turn out, you have the element of surprise in your favor, which, when dealing with an attack stat over 500, is lethal.
This really wreaks havoc in the Uber metagame. It looks strange, but really only a healthy Kyogre can stop it, along with the ExtremeSpeeders, of course (Rayquaza in particular). The EVs are up to debate, though, even if you maximize Special Attack it needs the sun to be strong in order to do large amounts of damage to Metagross. Even then, it most likely won't be an OHKO, so you will want to dent it a little first—about 15-20% to be safe. Also note that a lot of Groudon are now running Special Defense, so SolarBeam won't OHKO either, be sure to wear him down as well. ExtremeSpeed is an option if you want to be able to hit Rayquaza for nominal damage and have a chance against other Deoxys-A. All those Attack EVs are necessary to ensure an OHKO on most Lati@s, which is also what the optional Spell Tag is for. It's best if you hold onto this sort of Deoxys-A until the end of the match because his value is in the diverse way he sweeps rather than the pure force of something like the Choice Band set.
Pursuit is a decent option, as most people's first reaction upon seeing Deoxys-A is to switch out for something like Metagross or Groudon / Kyogre. There isn't really much else Deoxys-A can survive to do.
For a Choice Bander, max Attack, max Speed. For the Substitute set, max Special Attack, max Speed is probably best, Mild. On either of them, a +Speed nature is also good, because it beats out Exeggutor and other Deoxys-A (only with ExtremeSpeed, or it's pointless to beat out the other Deoxys-A, who will likely just ExtremeSpeed you, and if they don't have ExtremeSpeed, they switch out). Considering the rarity of Timid Mewtwo (since it beats nothing that's used on 95% of teams that Modest doesn't), you could go down to 360 Speed and still beat out Modest Mewtwo to give you more EVs for a mixed sweeper set.
Always use a -Defense nature if you're using two types of attacks. You obviously won't want to lower one of the attacks, and Deoxys-A needs all the Speed it can get. So it comes down to -Defense or -Special Defense. There isn't a used physical attack that Deoxys-A will survive, regardless of your nature, except maybe the rare Superpower Deoxys-D. However, Deoxys-A can survive Pursuit (if it doesn't switch) from Metagross and Knock Off from Deoxys-D. If you'll notice, all of these are Dark attacks, meaning they run off the special stat. Knock Off does 29-34% to Deoxys-A, assuming Deoxys-D has no Special Attack EVs. This is almost always a 4HKO. It does 32-37% to a -Special Defense Deoxys-A, which is almost always a 3HKO. If you stay in on a Metagross with no Special Attack EVs and a Special Attack neutral nature, you can sometimes survive even with 3 layers of Spikes down, and always with 2 layers down (72-84% damage). This is not the case for a -Special Defense Deoxys-A. Deoxys-A can also survive Lugia Ice Beam by 5% at the least if its nature is neutral, but a -Special Defense Deoxys-A often dies. Even Psycho Boost Lugia doesn't have a guaranteed OHKO without Special Attack EVs (lots of Lugia don't have any, because of all the defense needed).
Checks and Counters
Deoxys-D can do a moderate job against non Shadow Ball ones, but really, wow. This thing has amazing Attack and Special Attack stats, and a great movepool to abuse those stats.
Ninjask is faster than Deoxys-A if Ninjask is Jolly or if Deoxys-A isn't Hasty, and can OHKO with any of its attacks. It can only come in on Superpower (Choice Banded is a 3HKO), SolarBeam, or Calm Mind, though. It can actually damage many other Ubers with that STAB Bug attack, so it's not entirely useless outside of stopping a Deoxys-A sweep. It is still at risk of dying to ExtremeSpeed, however. Dodrio and Swellow can kill it with Quick Attack, and have a perfectly safe switch in on Shadow Ball, the most commonly used move on physical Deoxys-A, and can use Return / Double-Edge if Deoxys-A is Choice Banded, which seriously hurts most Pokémon. Arcanine can switch into anything Deoxys-A throws at it, save Psycho Boost, thanks to Intimidate, and use ExtremeSpeed, but Arcanine is a really easy switch out. Rayquaza is probably the best counter, since the Choice Bander is the most common, and a lot of people still haven't caught on to using Ice Beam as the last move, so it's a fairly safe switch. However, you have to beware of the Substitute / Ice Beam set, because it sets up a Substitute as you switch to Rayquaza, and then you have to switch out because of the Ice Beam threat. Pursuit Metagross can stop it after the initial kill for 100% safety (unless it has Thunder in the rain or Fire Punch in the sun and stays in), or can come in on anything from the Choice Bander but +Attack Superpower. With Spikes down, Choice Band Trapinch can come in after it kills something and use Quick Attack, unless it's using Choice Band ExtremeSpeed, in which case Trapinch dies even with max Defense.