> Rather, it's using the energy to deoxidize rust.

Exactly, really what they are storing is electrons.

Rusting the iron directly releases heat, which limits your efficiency to the delta-T of the process. Reducing steam to hydrogen and then converting the hydrogen in a fuel cell allows higher efficiency to produce electricity.