Предлагается на каждые 1-10 млн. записей/стираний ячеек EEPROM выполнять регенерацию информации в остальных используемых ячейках EEPROM. Или хранить константы не в EEPROM, а во FLASH - типа так надежнее.
Слегка подробнее здесь.
По жизни с такой проблемой не сталкивался (если предполагается более 1Е6 записей, имхо проще поставить FRAM).