Residual Power in Decoupling Capacitors
The situation you described is very typical for devices with low-power CMOS ICs. This is called "brown-out" conditions.

One simple solution is to add so-called "bleeding resistors" to power rails that cause the trouble. But in this case you will waste some power during normal operations, which might be prohibitive from battery life standpoint. 

More expensive solution (used in portable electronics/laptops) is to use active circuits (typically FET transistors) on power rails. The transistors  are controlled by a voltage monitor, which turns the FETs on when some main voltage rail drops below certain limit, and the FETs discharge the rails quickly.

Some voltage regulator ICs have a built-in "auto-discharge" circuitry.

In many cases it is sufficient to provide a robust hardware reset to CMOS IC after the brown-out condition, if IC has a well designed hardware RESET which overrides any residual "bad" states after Vdd is restored.