Hello Albinoni,
I think we first have to clear up some terms...
Completely discharging a battery in an application, may still leave some potential remaining in the battery. A fully discharged battery under these conditions will still show some voltage after the load is removed and it rests for a few minutes.
Completely discharging a battery, then shorting the + to the - terminals, will completely drain the battery and there will be nothing left.
All rechargeable batteries self discharge over time. Some much slower than others, but eventually they will all self discharge down to 0 Volts. While not the same as draining and shorting the battery, the results within the chemistry of the battery is the same.
Now we have to look at chemistries...
Lead Acid batteries have sulfate reactions that build up on the electrodes under discharged conditions. This sulfate build up limits the electrodes ability to contact the electrolyte. The result is reduced capacity and damage to the battery. The key is the amount of time spent in a discharged condition.
It is possible to completely discharge a lead acid cell to 0 volts under load, and if you immediately charge it back up, no damage is done.
The problem is that most lead acid batteries are made up of several cells. Once you have more than 1 cell, you now have to worry about balance between the cells. If one cell drains before the others, the others will try to reverse charge that cell, and most likely ruin it.
The problems associated with using multiple cells is the same with all chemistries. If you don't make provisions to balance your battery pack (made up of several cells), you will eventually drive a cell to reverse charge and it will fail.
NiCd chemistry prefers to be run completely flat, under load, to a loaded voltage of 1.0 volts per cell. If you plan to store the cell, you can short out the + and - terminals and store a NiCd cell that way. After storage, a cycle or two of charging and discharging will bring the cell back to its normal condition.
NiMh cells are run down to 0.9 volts per cell under load. Once the load is removed, the voltage will spring back up to 1.1 - 1.2 volts.
If you end up with a NiMh cell that is showing 0 volts resting, the cell is damaged. In an over discharged state, the electrodes inside the cell corrode. This results in impurities contaminating the electrolyte, and a loss of active electrode material. The cell is damaged. The longer the cell sits in this over discharged condition, the more damage is done.
When you purchase new NiMh cells, you should always check their voltage. If the voltage is above 1.0 volts, you are good to go. If they are below this, there could be some damage done, and you will have to do some testing to determine what condition the cells are in.
Moving on to Li-Ion chemistry. When you over discharge Li-Ion cells, the electrolyte oxidizes the electrodes and changes the electrolyte into something that has the potential to become a conductor. Shorts develop as a result of this electrolyte contamination. Once again, the longer the cell sits in an over discharge condition, the more damage is done.
Lead acid batteries prefer very shallow discharges. Their cycle life is rated on something like a 20% discharge cycle. NiCd, NiMh, and Li-Ion cells are rated on a full discharge under load to their respective cut off voltages. If you limit your use to only a 60 - 80% discharge cycle, you will get more life from your cells.
The problem with shallow discharges for NiCd and NiMh cells, is that the crystals left during the shallow discharge tend to bond together and create problems. Because of this, it is recommended to do a 100% discharge every 25 charge/discharge cycles. The full discharge breaks up the crystals and everything goes back to normal.
The problem with shallow discharges for Li-Ion batteries, has nothing to do with the battery itself, but everything to do with the "fuel" gage used by the equipment the batteries are installed in. You need to do a complete discharge of your computer battery pack, every once in a while, to re-calibrate the fuel gage.
So, the answer to your question is that it depends...
Tom