The absolute best cleaner in the game. Absolute best. Nothing stops Deoxys-A.
Shadow Ball and Superpower 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 for stuff like Kyogre that is 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 2HKOes Groudon and OHKOes Rayquaza, which is very useful. Defensive Groudon can sometimes take two Psycho Boosts due 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 two 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 Deoxys-A if it switches 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 four so that the Petaya will activate on the third Substitute, thus allowing Deoxys-A to withstand Tyranitar's Sand Stream for a few turns, but HP not divisible by four 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 (as you can attack from behind your Substitute).
Because the Choice Band set 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 your opponents will be acting on the assumption that it is 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 ExtremeSpeed users 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 it 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 Latios and Latias, 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 its value is in the diverse way it 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 to something like Metagross, Groudon, or Kyogre. There isn't really much else Deoxys-A can survive to do.
For a Choice Band user, max Attack and max Speed. For the Substitute set, max Special Attack and max Speed along with Mild is probably best. 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, and if they don't have ExtremeSpeed, they switch out). Considering the rarity of Timid Mewtwo (as 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 attacking stats, 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 nature, except maybe the rare Superpower from 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 Attack 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 Deoxys-A stays in on a Metagross with no Special Attack EVs and a Special Attack neutral nature, it can sometimes survive even with three layers of Spikes down and always with two layers down (72-84% damage). This is not the case for a -Special Defense Deoxys-A. Deoxys-A can also survive Lugia's 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 take advantage of 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, and 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 Deoxys-A with Quick Attack; have a perfectly safe switch in on Shadow Ball, the most commonly used move on physical Deoxys-A; and can use Return or Double-Edge if Deoxys-A is Choice Banded, which seriously hurts most Pokemon. Arcanine can switch into anything Deoxys-A throws at it, save Psycho Boost, thanks to Intimidate, and use ExtremeSpeed, but it is really easy to switch out of. Rayquaza is probably the best counter, as the Choice Band user 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-in. 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 Deoxys-A after the initial kill with 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 Band user but +Attack Superpower. With Spikes down, Choice Band Trapinch can come in after Deoxys-A kills something and use Quick Attack, unless it's using Choice Band ExtremeSpeed, in which case Trapinch dies even with max Defense.