Before you doing anything to your hardware, you may want to make sure that your routine that writes to EEPROM works reliably. Writing to EEPROM is quite timing critical and you may need to disable your interrupts for a short period of time.

As to monitoring the supply rail, it is better if you do it at the input stage of your 5V regulator. Most 5V regulator quits working when the input drops below 9V. You can set up a simple circuitry with a diode(using it 0.7V forward votage characteristic) and a voltage comparator to do the job.