This is easily done using only 2 bytes of RAM if you implement a 256 times over-sampling filter.
You allocate 2 bytes of RAM to form a 16-bit counter. If you look carefully, you will observe that the upper byte contains the full value of the 16-bit counter / 256.
It is this property that makes this filter so easy.
I'm not at my computer, so I'll try to describe what I mean in pseudo code. Let's call the two bytes that form the counter CntrH & CntrL. As described above, the 8-bit value for the final output is contained in CntrH.
First, subtract the old filter value from the counter.
CntrH : CntrL - CntrH
Now add the 8-bit value from the a/d converter to the 16-bit counter.
A2D + CntrH : CntrL
The filtered output is contained in CntrH.
This is a very slow filter. Therefore, you want to seed the filter upon initialization by taking one a/d sample and loading it into CntrH.
This slow filter means that you want to add new samples fairly quickly. A rough approximation is that your desired filter period takes 256 samples.
In other words, add new samples to the filter at the rate of 10 minutes / 256.
[Edit]
This is extensible by going to a 24-bit accumulator if you want to acquire the samples at a faster rate. This would give you a 2^16 (65536) times over-sampling filter.
Same technique as above but using 3 bytes: CntrH : CntrM : CntrL . As before, the 8-bit filtered output is contained in CntrH.
Given that you want the period to be about 10 minutes (600 seconds), you would accumulate your samples at 600 / (2^16) =~ 9.1ms
What you are looking for in the datasheet is the pin structure schematic (or diagramm).
It may look something like this:

What you see here in particular are the protection diodes which clamp input voltages to the allowed region. Often it is given as Vdd+0.3 V and Vss-0.3 V or something like that.
The 0.3 V is the voltage drop of the protection diodes. If you have a voltage higher than Vdd+0.3 V the protection diode will start to conduct and supply current to the rest of the circuit.
Your circuit and the controller is of course not supposed to work in that way. For example you could be reverse biasing your voltage regulator on the other side, if the power failure is caused by the input of the voltage regulator breaking down (details depend on the way your power circuit is designed). This can damage your voltage regulator.
Depending on the current draw of the other circuit the actual voltage might be quite a bit lower so the components won't work as expected. For example when driving 20 mA the voltage of the output is reduced by 1.3 V:

So running from 3.3 V you'd get 2.0 V at the output and only 1.7 V as the new VDD on the other side. Which might cause all sort of troubles (some chips work already, others don't).
I'm not sure on the protection side of things, but maybe a power supervisor which holds the MCU in reset until both voltages are OK might work, as you then can be sure that both are powered correctly.
If you need to have one running all the time you might use a supervisor on each side for the other side and turn off all lines between them if the state is not okay, but as the reaction won't be instantaneous (software involved) it might be too slow.
Best Answer
It's a very basic behavior of any generator. Load creates torque reverse to one that is driven by the power source. Imagine a small generator, like your own, connected to an electrical locomotive. No chance it will move!
Another way to look is by power. Power it limited at some point. Mechanically it is rotation speed times torque, electrically it's voltage (speed times a factor) times current. When no load applied, mechanical power is completely wasted on mechanical losses. If load is applied, electrical power is no longer zero, so mechanical lisses must be reduced, and it means less speed.