These guys are quite similar to the air elemental (reviewed years ago), so expect frequent comparisons.
Small Storm Elemental
Compared to small air elementals (which got +1 LA), small storm elementals have more constitution, less dexterity, less natural armor, a stronger slam, a considerably lower speed, no Improved Initiative, and better special abilities, such as the awesome Thunder and Lightning. While it seems that they're better at low ECLs, I can't help but feel like the air elemental is more viable at higher levels where 100 ft. fly speed is more relevant than 1/round 1d4 electricity damage. Even so, +1 LA here (but speak up, ones who'd prefer +0!).
Medium Storm Elemental
+0 LA, just like their airy counterparts. The raised fly speed is nice, the strength boost is too, and while the dexterity reduction hurts overall this remains on par with the air elemental.
Large Storm Elemental
8 RHD? No.
Huge and Larger Storm Elementals
No. Just no.