Well, couple of suggestions...

The first is to oversize the PICs PSU and have about a two-second reserve... when it detects Power-OFF, it dumps the relative information to EEPROM in the reserve time. Saves saving to EEPROM every minute.

Another is just to keep track of hours. I made a decision on a piece of equipment that is ON for it's entire life only to save hours. If there's a power-outage, yes I'd lose some minutes, but since the timekeeping was for an elapsed Service Timer, plus or minus a couple of days (or even weeks) at the end of a year or two is neither here or there in the great scheme of things.

Another is to use any of Microchips micropower PICs (even a PIC10F series would do this) with an on-board battery just for storing the timekeeping. Don't want to use a Battery? ...then any handy piece of fruit or vegetable with dissimilar metals would do.

A fourth, (did I say a couple of suggestions?)... is to use an external RTC like a DS1307... it has a few bytes of internal RAM (accessible via I2C bus) which is backed-up from the Battery. Use that to store your elapsed time as it doesn't suffer from the WRITE endurance problem.

A fifth... use external memory that doesn't have the problems of serial EEPROM - eg Ramtron's FRAM...

A sixth... etc etc...

Melanie