Lithium Ion charging problems - power outages
I am not aware of how often this happens, but it shouldn't.

One possible cause is that the open circuit voltage of the battery is enough to hold the charger in the "fully charged - wait from battery voltage droop" state. This should not be allowed to occur and is easily overcome in a good design - see below.

A more likely reason is that the charger IC or charger is poorly conceived or designed and that a startup transient condition occurs which discombobulates it. An alternative is that this is a purposeful design choice aimed at increasing notional safety and perhaps avoiding liability claims. 

Of interest in researching what is wrong would be knowing the voltage Vbat just before power on, and the effect of loading the battery with a bleed resistor sos that it trickles down. A resistor of substantial draw could be added to 'hurry things up'. IF this works a larger resistor could be added long term.



Longer: 

The situation that you describe is easy to detect and manage and any charger circuit and IC worth its salt should handle it OK.
Unlike some battery chemistries whose charge characteristics need to be determined by observing dynamic behaviour, a Lithium Ion cell's charging requirement can be determined by it's behaviour either statically or after a very small test time period.

While super arcane chargers (which may or may not produce super arcane results) will build on the following, a LiIon charger is reasonably fully defined by the steps below.
 LiIon and LiPo have !~~~ the following values.  Will be fine tuned in practice EXCEPT Venough > 4.2V is VERY unwise. 
Vfatal ~ 2V
Vtoolow ~= 2.5V
Venough ~+ 4.2V. (4.1V for longer life, 4.3V for vent with flame.)
K - 0.5 to 0.05. Smaller = more capacity and shorter life. K=0.25 probably about right.
Vtopup ~= Venough - 0.1V


i  Vbat &lt; Vfatal - walk away
ii Vbat &lt; Vtoo low. Charge at low rate )(say C/100 until Vbat rises to >= Vtoolow)
iii Vtoolow  &lt; Vbat &lt; Venough. Charge at C/1 rate.
iv Vbat = Venough.
While not letting Vbat rise above Venough
charge while Ichg >= (C1 rate) x K
where K is a predecided fraction of C/1. eg 50% or 25% or 10% or whatever.
v  When Vbat = Venough and Ichg drops to 1/K x full charge rate, terminate charging  COMPLETELY
Remove Vchg from battery.
DO NOT float battery at Vchg even if Ichg is very low.
vi Monitor Vbat and when Vbat falls to say Vtopup restart step v, charging at up to C/1 if needed while holding at &lt;= Venough until Ichg again falls to C/1 x K


IF the battery is in state Vbat = Venough when power is returned the charger MAY start in step vi and hand there until Vbat drops. For this to happen the battery would need to be at about 66%+ capacity.