Exactly correct on the "deep discharge" for Lithium Ion and Lithium Polymer. They actually go negative and are often unrecoverable if they reach that state. That's why you leave them around 40% to store them.
NiCads are old technology at this point. They're cheap. Toss 'em and get new ones if they screw up. NiMH that I spoke of are basically the replacement for NiCads. If treated badly they will often exhibit reduced capacity. However if you cycle them about 3 times (charge full and then discharge full, rinse and repeat), they typically recover full capacity.
