I feel the need to talk about Pokemon so I'm very happy that this came up because I theorycraft to shit about Gen5 meta
Most of those legendaries you listed are not considered "ubers" and are not banned from normal play. In fact, most legendaries don't have especially great stats. The ones that are banned to ubers....
Deoxys A (glass cannon)
Tears through most holes in the Ubers metagame, especially given the presence of Life Orb. However, it is correct that Deoxys-A is pretty much the epitome of Glass Cannon - shitty defensive typing in Ubers (lels pure Psychic?) and abysmal defensive stats (50/20/20 don't be foolin' no one) mean all strong users of Choice Scarf sets, Mach Punch and Vacuum Wave pose as good checks to the speedy menace. However, keep note that +1 90 base speed Pokemon can not outspeed maximum speed Deoxys-A. Packing Scizor or Metagross on a Deoxys-A that doesn't have HP Fire is also a good idea, and Lugia can also tank Deoxys-A and OHKO it back.
Deoxys S (Mediocre durability--badly distributed stats for it)
Deoxys-S's worst enemy is the fact that Team Preview exists - allowing people to easily counter or check Deoxys-S before the game even begins, since you would be downright stupid not to play Deoxys-S as a lead in ubers metagame; as a suicide lead or not. Mostly, people run Deoxys-S on the support since it's capable of using dual screens, Stealth Rock, Spikes, Taunt, Magic Coat, and a whole slew of other useful moves for support. However, it's got some mediocre offense, ironically its best options on the offense being ExtremeSpeed for other Deoxys (of A or S variety) and Fire Punch (for the ever annoying Forretress lead). Other than that it's not very overwhelming. I guess.
Lugia (Unholy tank; and takes half-damage from grass, and most EV builds pour even more into defences. Err...yeah, this is strange--you sure it was level 100 with EVs?)
Crits are bullshit lelelelele
Did you know Lugia has Multiscale?! lelelelel (Though sadly Multiscale+Roost is illegal, so you need to rely on Recover instead)
Don't really need to say too much about Lugia that hasn't already been mentioned - it has ridiculous bulk; only a few things even scare it (Dark-types come to mind, as does Kyogre Water Spout, Zekrom Bolt Strike, and Kyurem Ice Burn all have the potential to ruin Lugia's day). It can phaze with Whirlwind/Dragon Tail, and has Toxic alongside its bread and butter move: Roost. For defensive purposes, Lugia can also pack a Sub or Reflect, which just further improves its massive bulk.
Darkrai (Mediocre durability--kind of like Deoxys S but not as bad)
Darkrai's major advantage is that it's Dark type in a tier where lots of things take super-effective or neutral damage to the Dark type. 90/135/125 offenses is really solid, especially considering that it has its signature Dark Void, which is the second most accurate Sleep-inducing move before Spore.
Dark Void
Dark Pulse
Focus Blast/Nasty Plot
Nasty Plot/Substitute
This is the set that Gen 4 players should recognize if they knew about Darkrai's potential as an incredibly powerful sweeper. It has access to a great way to set up and destroy the opposition, and its access to Focus Blast/Dark Pulse allows it to deal heavy damage to almost everything in the tier. Only two Pokemon resist the combination of attacks: Heracross and Toxicroak, with the former pretty much being one of the only reliable checks to Darkrai. Heracross takes the Dark Void happily and Sleep Talks, either 2HKOing or OHKOing back with its STAB moves thanks to Guts. Other than that, Darkrai's got great offenses.
Arceus (Fantastic tank, but as you mentioned there were special circumstances here)
Arceus having Multitype gives it a bazillion options, pretty much, and what Plate the player chooses
usually dictates what set Arceus is going to run, and the sheer unpredictable factor of which Arceus is going to come out until it does come out makes Arceus very scary. Of course being able to OHKO an Arceus takes some considerable luck if you're running Pokemon who aren't: A) offensive behemoths or B) abusing the weakness of the type Arceus currently is, but eh.
Mewtwo (Much more known for ridiculous speed and offence than durability, but his durability isn't bad)
Mewtwo's 106/90/90 defenses are decidedly reasonable for Ubers.
Mewtwo gained a very powerful and new toy this generation - Psystrike. It's a 100 BP Psychic move that hits the Defense stat, but runs off of Mewtwo's Special. And only Mewtwo gets it (everyone else gets Psyshock, the 80 BP variant). In fact, this one single addition is what makes Mewtwo incredibly terrifying this time around. Combined with ridiculous speed, Mewtwo now effortlessly puts dents into Chansey and Blissey (especially with Calm Mind, a +1 Mewtwo pretty much OHKOs most things in general at this point) and has ridiculous coverage, Ice Beam/Fire Blast/Aura Sphere and more. Furthermore, it gets Unnerve as its Dream World ability, which allows an offensive Mewtwo to completely trivialize Chople Berry T-Tar, Yache Berry Garchomp and Wacan Berry Manaphy. Did someone mention Custap Berry Wobbuffet? Well now that ain't working anymore either.
Fun fact: A Choice Scarf Shadow Tag Chandelure can and will ruin Mewtwo's day with an Overheat under the Sun. Steel type Pokemon will give Mewtwo a hard time as well if Mewtwo doesn't have Fire Blast. If it does, welp. Psychic Arceus can do something about Mewtwo too, unless it has Shadow Ball. Then welp.
I've got some experience with Random WiFi battles on Pokemon BW, if anyone wants to hook up for some WiFi battles then just shoot me a message on the boards here or on IRC (I'm Mikan or some other stupidly girly nick)