Memory in NiCd is a well understood problem, and it is related to two issues. How fast you try to discharge the battery, and how far you discharge it.
Low drain applications (Essentially Capacity in Mah/current demand)>10, and you will never see it. The load resistance is very high compared to the battery, so even fairly large changes in internal resistance of the battery tend are still very small compared to the load, so they are unnoticed. If I had a battery with a .1 ohm internal resistance, and I place a 2 ohm load on it, doubling the internal resistance has little effect, total load goes from 2.1 to 2.2 ohms.
Unfortunately mobile phones, big flashlights etc often are very high drain applications (Capacity/demand=1 or less). In these applications, the external load resistance is similar to the internal battery resistance, so any changes are much more noticeable. If I take that same battery and put a .2 ohm load on it doubling the internal resistance takes the total load from .3 to .4 ohms, a 33% increase,
and a 33% decrease in energy delivered to the load
Memory is not actually a loss of capacity, it is an increase in internal battery resistance. Typically NiCd's have very low internal resistance. This is what makes them attractive in high drain application, plus the fact that will tolerate a great deal of abuse.
This very low internal resistance is achieved by giving the electrodes huge surface area. They are often sintered, which means they are made of powdered metal that was heated just enough to make it stick together. Think of it as the difference in surface area between a 1 pound rock, and 1 pound of sand. The sand has orders of magnitude more surface area. If I shrink the particles, the volume is proportional to the cube of the radius, the but the area is proportional to the square. So if I half the radius, it takes 8 times as many of the smaller object to have the same volume and mass, but each of them has 1/4 the area, so halving the particle diameter doubles the suface area for a given mass. This is in fact how it has been possible to raise NiCd capacity from the original 450mah in the 1960's for an AA, to 1000mah in the same size AA cell today.
The charge is stored in the form of chemical energy on the electrodes.
If you don't fully discharge the battery periodically, the crystalline structures that are the chemistry tend to combine and form larger structures. The Surface area to mass ratio goes down as the cube of the diameter, so even small increase in average crystal size greatly reduce the available surface area on which the reactions that convert the chemical energy back into electrical energy occur.
This manifests itself not as a loss in capacity, but an increase in internal resistance, so if you are depending upon the ability of the battery to provide very high current, it must keep a low internal resistance, which it may no longer have.
Discharging NiCd's is a delicate process if you are dealing with more than 1 cell, in fact many cell phones that used NiCd's shut down long before the battery is completely dead. They sense that one cell in the pack is fully discharged, for example a 6V pack is only putting out 4.7 volts means one cell is fully discharged. If you continue to draw power from the battery, the fully discharged cell is reverse charged, and that is the number one killer of NiCd cells.
OTOH, Lead Acid cells come in two flavors, those that tolerate deep cycling well (often used in electric trolling motors), and those that tolerate overcharging well (automotive batteries), however if you use a deep cycle battery in an automobile, you are going to be unhappy, it won't last long. If you use a battery designed to tolerate overcharging in a deep cycle application,you won't be real happy with the lifetime either.