A set of non-volatile storage elements is divided into subsets for erasing in order to avoid over-erasing faster erasing storage elements. The entire set of elements is erased until a first subset of the set of elements is verified as erased. The first subset can include the faster erasing cells. Verifying the first subset includes excluding a second subset from verification. After the first subset is verified as erased, they are inhibited from erasing while the second subset is further erased. The set of elements is verified as erased when the second subset is verified as erased. Verifying that the set of elements is erased can include excluding the first subset from verification or verifying both the first and second subsets together. Different step sizes are used, depending on which subset is being erased and verified in order to more efficiently and accurately erase the set of elements.