| You never ever *completely* discharge any battery.
That's not precisely true, but it's a good rule of thumb.
You can completely discharge any NiCd or NiMH cell without damaging it. The danger is that if you have several cells in series (which they usually are) and you discharge that and they're not perfectly matched, you end up reverse-charging the weakest cells, which make them even weaker, weakening the entire pack.
But the car guys sometimes will put resisters in parallel with each cell in their battery pack so that they'll fully discharge after a race -- they charge the battery right before the race, race, and then the resistors slowly drain off whatever is left on each cell so they can be fully charged later. (NiCd/NiMH cells perform best if they were just freshly charged.)
LiPo and lead-acid batteries, on the other hand, are damaged by completely discharging. With lead-acid batteries, the damage isn't too severe if you charge it up immediately after, but if you leave them discharged for a while, they won't accept a charge anymore. With LiPo cells, a single full discharge can ruin the cell.
And primary cells, you completely discharge them any time you want -- since they can't be recharged, there's no real reason not to fully discharge them if you can (unless they do nasty things like leak when this happens.)