I have given this consideration for a project that I am working on as well.

Realistically how often is the status of the relays going to change ?

How many times per day in total ?

The EEPROM typically has a life of 1 million cycles which can be used up very quickly with frequent updates, or may well outlive everyone on this list if the frequency of updates is quite low.

What is the designed lifespan for your product ?

1 second = 86400 per day = 11.57 days
10 seconds = 8640 per day = 115.7 days
30 seconds = 2880 per day = 347 days
1 minute = 1440 per day = 694 days
5 minutes = 288 per day = 9.5 years
10 minutes = 144 per day = 19.0 years
30 minutes = 48 per day = 57.1 years
1 hour = 24 per day = 114 years
2 hours = 12 per day = 228 years
6 hours = 4 per day = 685 years
12 hours = 2 per day = 1370 years
24 hours = 1 per day = 2740 years

If there are less than 50 updates per day then I wouldnt bother trying to detect power failure as its going to take over 50 years to kil the eeprom, even updating every five minutes will give you the best part of 10 years.