Good link. IMO, the article falls into the trap of allowing "memory" to mean any loss in overall battery capacity, as opposed to loss in capacity due to not fully discharging the battery. My explanation follows, and I believe it is consistent with your linked article as long as we ignore the distinction in the definition of "memory".
The "memory effect" is so named based on the theory that the battery "remembers" its discharge point as full discharge. Thus, it loses capacity if it is continually discharged to a level above full discharge - this level becomes its effective full discharge.
I don't have any links, but I recall that the original "memory effect" was found in the battery array of an orbital satellite. It had a very regular cycle of charge/discharge as it collected solar energy in sunlight and ran from batteries while in the Earth's shadow. It was designed to have excess capacity, so the batteries were never deep-discharged. Over time, it was observed that the satellite's batteries were losing capacity (from readings sent to Control).
This is the only laboratory proof that the memory effect exists as stated above. The loss in capacity was present, but really not very large.
2 things typically cause loss in capacity for NiCd/NiMH batteries used by consumers - overcharging and cell reversal. Typical cheap chargers either pump a fixed current into the battery or (a little fancier) have a timer, after which it drops the current to a "trickle charge". This overcharging overheats the battery from within, which rapidly reduces capacity and kills the cell. Smart microchip-controlled chargers ($25-50) run much higher currents while the battery can handle it, slow as it reaches capacity, and finally shut off completely. Cell reversal occurs when an individual battery is drained to 0V (full discharge for NiMH is roughly 0.8V) and beyond, i.e. being charged by the other batteries in the device. Cell reversal is a great way to kill batteries.
"Deep discharging" and "exercising" a battery with reduced capacity (not completely dead) does generally improve its capacity, but not to its original state.
When rechargeables first hit the market en masse, marketed as drop-in alkaline replacements, ignorant consumers with crappy chargers killed their batteries and propagated "OMG memory effect NiCds suck." My guess is that "exercise" was publicized as a stopgap, and the opposite of the solution was assumed to be the fault.