However, if it is rusty, isn't the steel already oxidized, that is burnt?
Yes, that is correct enough for this level. Rust is the result of iron reacting with oxygen in the presence of water. The amount of oxygen available determines what iron oxide molecules will form. If enough oxygen is present the end result will be the same as if it were burned.
Sealing the steel wool in an oxygen-free ziploc will prevent rust. As for "partially" rusted the steel wool being a better tinder, that doesn't make sense. The un-rusted steel wool is chemically more reactive than steel with even a little bit of rust. Think of unrusted steel as a 17yr old boy...it REALLY wants to react with that cute, redheaded oxygen molecule. But once he does he's blocked (a bit anyway) from going after those twin Swedish exchange-student oxygens...
However, this *might* not be the case with using steel wool in combination with a battery. In this process the steel wool gets hot because electrons are passing through it. The steel has a certain resistance to this flow of electrons and this friction produces heat. If you increase the friction of the elctron flow more heat will be produced. The slightly rusted steel wool probably has a higher friction and so the stuff heats up faster to a higher temperature. I'm just guessing on this, though.
-Blast