Lithium-Ion rechargeables shouldn't be totally discharged. They perform best when kept topped-up. Their lifetime is virtually independant of the number of charge/discharge cycles they undergo. They have no 'memory' effect.
Here's a quote from Wikipaedia -
"Unlike NiCad batteries or NiMH batteries, lithium-ion batteries should be charged early and often. However, if they are not used for a longer time, they should be brought to a charge level of around 40%. Lithium-ion batteries should never be "deep-cycled" like NiCd or NiMH batteries"
The full article is
Here. A Google search will bring up loads of other sources giving the same advice.