My knowledge of this comes partly from personal experience and partly from lots of reading of various sources. Nonetheless, there seems to be considerable confusion, and I do not claim to have perfect answers.
It seems clear it is better to discharge NiCad batteries nearly completely before recharging. Otherwise they suffer what is referred to as a "memory effect" that reduces their ability to deliver a full charge. Some NiCad rechargers can be set to further discharge a partially discharged battery before charging it. This is generally known as "conditioning" the battery.
It seems clear it is not good (indeed very destructive) to completely discharge the lead-acid battery in your car. A single case of complete discharge can ruin the battery.
It is not clear that the degree of discharge before recharge has much affect on the lifetime of NiMH batteries or Li-ion batteries. Most sources say these batteries do not suffer a "memory effect" and can be deeply cycled or shallow cycled without long term consequences. Nonetheless, the batteries do have a finite number of cycles before they need to be replaced. The point is that this number of cycles does not seem to relate nearly as much to the depth of discharge for these batteries as it does for NiCad or lead-acid batteries.
I have a fairly large number of NiMH batteries I use in a digital camera. CD player. GPS, Celestron Telescope, etc. I have run charge/discharge cycles on these in which I have plotted (with a chart recorder) many charge discharge cycles under various depths of discharge. I have not been able to discern any pattern that seems to be better or worse for these batteries, so I am inclined to believe the advertisements that claim you don't have to follow any particular regimen for these batteries.
I am using a recharger specifically designed to recharge NiMH batteries (Maha is the manufacturer). Rechargers specifically designed to recharge NiMH batteries recharge at a high current, then switch to a type of trickle current when the battery is nearly charged. But it is more complicated than that. The microprocessor initially charges the battery with a high current that is pulsating. Then it switches into a steady mode and monitors the voltage over time. When it detects a voltage peak it goes into a "trickle mode" in which it alternates no charging with low charging (rather than a continuous low-level charging). It is something in the neighborhood of 10 minutes of no charging cycled with 2 minutes of trickle charging.
This shows that battery manufactures are playing with recharge methods in an attempt to squeeze out more recharge/discharge cycles before the batteries needs to be replaced. In my experience they are having some degree of success with NiMH batteries. I do not have much experience with Li-ion batteries.