1. A method for operating a non-volatile storage system, comprising: applying voltage pulses to a substrate of a set of non-volatile storage elements in each erase operation of a plurality of erase operations over a first portion of a lifetime of the set of non-volatile storage elements, each erase operation over the first portion of the lifetime uses a first value for an erase-verify level; based on the applying, determining when a condition is met for adjusting the erase-verify level, the condition is met when an amplitude of voltage pulses which are applied in at least one of the erase operations over the first portion of the lifetime exceeds a limit; and when the condition is met for adjusting the erase-verify level, using a second value, higher than the first value, for the erase-verify level in place of the first value in each erase operation of a plurality of erase operations over a second portion of the lifetime; the set of non-volatile storage elements include multi-level storage elements which are programmed to at least first, second and third programmed states using respective program-verify levels; and in the second portion of the lifetime: at least two of the respective program-verify levels are incremented, by different amounts, relative to the first portion of the lifetime.