No, there's no memory effect in lithium ion batteries, and the do not need to be fully discharged - or even partially discharged - before recharging. They don't really care whether they are fully discharged or not before charging. There is a limitation that if they drop below 2.7V per cell, they start to break down internally which causes permanent damage to the cell, but all manufacturers of lithium ion/polymer cells guard against this with internal circuitry so the end-user doesn't need to worry about this problem.
The biggest secret with lithium ion (and lithium polymer) batteries that I never see anyone talk about is that they just wear out whether you use them or not. They oxidize over time, so that, whether you charge them or not, or leave them on a shelf and never touch them, after about 2 years they will hold about half what they could hold when they were first manufactured. And they also suffer from an internal resistance issue that makes this problem even worse than just the capacity loss per year loss.
This is described very well in the first paragraph of the "Disadvantages" section of the wikipedia entry:
http://en.wikipedia.org/wiki/Lithium_ion_battery
A unique drawback of the Li-ion battery is that its life span is dependent upon aging from time of manufacturing (shelf life) regardless of whether it was charged, and not just on the number of charge/discharge cycles. So an older battery will not last as long as a new battery due solely to its age, unlike other batteries. This drawback is not widely published.
They lose about 20% capacity per year, no matter what you do. So after about 2 years, most lithium ion and lithium polymer batteries need to be replaced. This also means that you want to try to get "fresh" lithium ion/polymer batteries when you buy them. So I would never recommend buying a used lithium-ion or polymer battery.
But aside from the fact that they just gradually die, there's really no penalty with lithium ion based batteries. You can discharge them completely and then recharge them, or keep them charged all the time with very little difference in terms of how long they will last. The wikipedia article mentions a problem with "deep discharge", but I haven't seen this problem myself.