Soft-power on/off with ATMega/Relay causes brown-outs and unexpected voltages
You're much better off using a FET to switch the power than a relay.  The current spikes from a relay coil can give you all kinds of supply problems.  The FET is also far more efficient.
U303 (and likely the other linear regulators) are heating up because each one is dissipating about four times as much power as they're delivering to the load.  It would be far better to use a switcher to get into the 5-10V range, and run your linear supplies from there.
You're probably seeing stored charge in the caps.  In the 1.3V range, the devices may lose any capability of switching on, and present a high impedance, allowing the caps to stay charged.  A bleeder resistor in the 10K-100K range would probably get rid of that.