Ho-hum...couple of notes Dark_Azelf:
One, Zap Cannon is not at all acceptable on Registeel, especially since it's so sturdy. A five-PP move that misses half the time on a pokémon that needs to keep bapping until the end of time? No, just no. Unless you've got 'No Guard' around you should never go below 70% accuracy in damaging moves. If you want to paralyze, go with Thunder or Thunder wave. Also, why in the name of all that is sweet and sugary are you sticking Speed on something with base 50 and a -Spd nature? Pool it into Atk or SAtk. O= Toxic should also come with a little warning label these days because Breloom and Guts/Quick Feet sweepers abuse it so badly that you might end up helping your opponent rather than hindering them. :\ Oh, and Curse is only for Curseice (Explosion/Ice Beam/Earthquake (or Focus Punch)/Curse, as I recall), don't think it's really that useful these days.
SMALL EDIT: Awwright, so apparently the Zap Cannon thing is based on the popularity of Tyranitar and Hippowdon. (Who drop Thunder to 50% accuracy) I still wouldn't recommend using it unless you have one of those two on your team, and even then...sorry, but that moves just violates my religious principles. ~_~
Anyway, I don't really give a damn about Regirock but Registeel has proven itself to be quite cool, so I actually bothered to run some numbers on it:
Registeel @ Leftovers
Sassy Nature (+SDef, -Spd)
EVs: 204 HP / 136 Atk / 56 SAtk / 112 SDef
Thunder
Ice Punch
Rest/Explosion
Sleep Talk/Thunder Wave/Counter/Stealth Rock
Ironically, Registeel pwns Regice's buttocks at special walling these days. Rest and Sleep Talk pretty much go together because of the current environment, but if you go with Explosion it opens up quite the variety of support moves. With this spread, Registeel 2-hit KOs standard Dragonite, Salamence, Garchomp, Gyarados, and Skarmory. The SDef is also enough to wall out Starmie, Porygon-Z (Unless it's Nasty Plot boosted), Kingdra, and Specsmence (unless it hits you with Flamethrower) and can strike back with Thunder, T-Wave or Ice Punch (or Explosion if Registeel has served out its purpose). If you don't give a damn about 2-hit KOing Garchomp or Dragonite and aren't running Explosion, you can dump those Atk EVs into SDef and still average a 2-hit KO on Salamence, though just barely. There are probably some magical Def numbers that make Counter tick, but I can't be bothered to run them at the moment. xP
