deep discharge and the memory effect
First off, there is a difference between "deep discharge" and "drained dead." If you drain a ni-cd cell completey dead, you are decreasing it's life, Not a lot, but the effect is cumulative. Worse yet, if you have many cells in series forming a higher voltage string, one cell is likely to drain off before the others, and may develop a negative voltage ("cell reversal"). This can kill a cell very quickly (you actually boil the magic gasses out of the emergency vent), and that's that - you now have a dead cell, and a useless battery that will soon be dead if you don't do something about the dead cell (usually uneconomical for small handheld batteries).
However, if you have control circuitry which will cut power before this happens, a deep discharge is recommended by many ni-cd (formerly most/all) manufacturers in order to prevent memory effects. However, it should be noted that true "ni-cd memory" is actually a very rare phenomenon, only seen when a cell is consistently used within a very small percentage of it's capacity. Far more common, and often mistakenly identified as "ni-cd memory" is simple voltage depression due to overcharging and age. This is the same cell aging issue mentioned in this article, and not one that is limited to ni-cd chemistry. Contributing to the confusion is that deep discharge and recharge may help recover some of that lost capacity, so the "folk remedy" for ni-cd memory is the same as a real remedy for the far more common problem of voltage depression.
Finally, ni-cd cells that sit a long time can form conductive crystals called dendrits internally that eventually short out the electrodes. Regular drain and charge cycles will dramatically slow dendrite growth. Once dendrites have reached a certain state, they can be sometimes be "cleared" by hard charging the cell, but it's a temporary fix at best, as the crystal forms again fairly quickly. A cell showing signs of dendrite growth (failure to hold a charge for) should be considered EOL or near EOL even if temporarily recovered.
In summary:
- Ni-cd memory might as well be a myth for the typical consumer.
- Voltage depression, however, is real.
- Deep discharge can be good, but isn't needed everyday
- Drained completely is BAD
- Regular use is good (@Arclight, I'm looking at you)
- Once damaged, there is no real way to fix a cell