As you said the programs are stored in the EEPROM and it shouldn’t have got lost even if power is lost many times. I am not really sure how it happened — it could be that some weird condition triggered a factory reset which wiped out the programs.
I found a fair amount of ‘buzz’ on various forums regarding corrupted EEPROM data on ATMega applications. It involved the execution of instructions when voltage was below spec. I suspect that rather than going on or off my line voltage may have been low for several seconds. The EEPROM data in my ONKYO receiver was also corrupted.