Completely discharging you battery is bad for all batteries (well, maybe not lithium-hydrogen batteries, but if you have those in your laptop, you know what you're doing anyways).
The practice originates with NiCad batteries, due to a confluence of unfortunate design decisions. The common-knowledge belief that NiCads loose capacity if not fully cycled is false.
Basically, the shallow-cycling of NiCad batteries results in a depression of the discharge curve, resulting in many electronic devices which use NiCads incorrectly reporting the battery as being empty. Note that the capacity of the cell is not significantly reduced, the cell voltage is merely depressed by a small amount. The fact that the major portion of the NiCad discharge curve is very flat leads to a small change in overall cell voltage causing a large change in the battery "Charge State" readout.
Note that the memory effect occurs only with NiCads, and was never actually even present in any other cell chemistries. The conflation of battery types, and naive assumption that all batteries are the same is what has lead to the belief about all batteries needing periodic cycling.
It is probably more accurate to think about batteries as being able to store and release a certain amount of energy, rather than being able to withstand a certain number of cycles. Whether this energy is release in 500 half-cycles or 1000 quarter-cycles is largely not relevant (An increased depth of discharge will actually reduce the total overall energy capability of batteries, though not significantly unless the batteries is discharged completely).
The manufacturer's that state that you should fully discharge and recharge your devices battery are stating this solely so that the internal battery charge measuring electronics can properly calibrate themselves. Basically, over time, the charge-state measurement will drift due to slight variance in the efficiency of charging and discharging the battery (basically, it's an integrator). A single full-cycle lets the electronics accurately measure the battery capacity without having to guess about the battery condition. The fact that if not fully cycled, battery measurement electronics will inaccurately report the battery state has led to the perseverance of the Memory Effect myth. The battery has not actually changed, the electronics are merely reporting an incorrect charge state.
As far as I know, the biggest cause of gradually reducing battery life in electronics is time. Lithium batteries actually have a shelf-life rated in a few years, whether they are used or not. Proper storage practices can extend this shelf life, but they will decay over time, no matter what use you put them through.
Deep cycling lithiums is actually quite bad for them, actually. Don't do it unless you have to (try to stay above 20% SOC).
Note: I am skipping a few things, like the issues with whisker growth in nicads. See the below link on NiCad for further reading.
See:
http://en.wikipedia.org/wiki/Memory_effect
http://en.wikipedia.org/wiki/Nicad