If lithium ion batteries supposedly do not suffer from the "memory effect" why is it still recommended that a fully charged battery be used completely before recharging and that it be removed while the mobile device is plugged in?
Rechargeable batteries of all types suffer stress when deeply discharged. Li ion batteries are particularly sensitive to this, and will have deep discharge protection circuits built into the packs. (Discharging a li ion battery beyond the cut off point can destroy the internal structure, severely degrading the charge holding ability, and may result in the battery exploding when recharging is next attempted).
In the case of Li ion - the carbon and cobalt electrodes that absorb the lithium ions change their molecular and crystal shape when the li ions move. The more li ions are removed from the anode during discharge, the more stress gets put on the crystal structure. Too many deep discharges, and the crystals start to disintegrate. Light discharges put less stress on the crystals, and so they degrade more slowly (you get a lot more light discharges than deep discharges - in general, you get more total life with light discharges - i.e. you get 2-3x as many 50% discharges as 100% discharges).
The 'memory effect' you sometimes see with Li ion - isn't really a battery issue (indeed, no consumer batteries ever really got 'memory' - not even NiCds*). It's a 'low battery' detection issue - in the case of Li ion, microprocessor controlled charge guages may lose accuracy if the battery isn't deeply discharged periodically.
* - the 'memory' in consumer grade NiCds is a 'low battery' detection issue. A used NiCd battery has a lower voltage than a 'new' NiCd. A deep discharge will temporarily boost the voltage. Cheap battery health monitors wouldn't compensate for this and with a 'used' NiCd would cut off when the battery still had substantial charge remaining (because the voltage was too low to power the device).