Hello,
When flash is being erased and re-programmed with data held in RAM, the Vdd supply should be able to hold for a sufficient period to complete the process, should power be removed during the process. This may involve increasing the bulk capacitance at the output of the voltage regulator.
Additionally, it may be useful to provide an "early warning" of the removal of power, to avoid commencing the erase process for such an event. If using a linear voltage regulator, this might be done by sensing the voltage at the input of the regulator, on the anode side of the reverse polarity diode, to avoid the delay for the discharge of the regulator input capacitance.
Maybe there is also the possibility of writing the data to two different flash sectors on power up, with one of them having been pre-erased during the previous power down. The write process alone should be much faster than an erase, followed by a write.
Regards,
Mac