What rechargeable battery is suitable for severe frost (−10 Celsius and below)?
From what I've seen, the lithium ferro-phosphate types (check out A123) have better low temperature performance than most.  I won't say "good" performance because really no battery is good in the cold compared to room temperature, but some not as bad as others.

The first generation of popular hybrids, like the Toyota Prius and the Honda Civic for example, used NiMH batteries.  The newer lithium were known at the time but not deemed ready for volume end use.  The next generation is being designed with these batteries.  If I remember right, the Tesla and Chevy Volt use them already.