I've been told that EEPROM can work fine, through many write cycles, until the power is turned off.
Yes this is true. Back in 2001 ATMEL were selling a flash part that they claimed to have a endurance of 1000000 write cycles. I was involved in testing them and found the real life was only 80 to 120 cycles if you powered then down between writes. That was flash not eeprom but I imaging the same applies.