Kyogre - keep HP Grass, it says hello to Swampert and Quagsire.
Groudon - Eruption/Fire Blast/Overheat over Flamethrower, Groudon's Special attack isn't the greatest, so bump up the power of the fire moves. HP Bug works over FT too (die Celery!)
Rayquaza - HP Bug is a physical move. I'd rather lose Rest for another attack, Brick Break/Earthquake/Rock Slide works better.
Deoxys - Choice Band only bumps up the attack power of Shadow Ball, I'd lose it for a Lum or something else.
Registeel - Quick Claw is the other option for getting that first-strike Explosion. Otherwise, Leftovers is fine. As for the attacks, at least give him a way to damage things...
[email protected]
EV: 252 HP, 129 Def, 129 Sp Def
Nature: + Def, - Sp Att
Amnesia
Explosion
Curse
Earthquake/HP Steel/HP Rock
Lugia - I guess if you're gonna Toxistall/Toxishuffle, use Aerial Ace over Aeroblast, gives you more PP to use.