The memory gets damaged for every single erase operation. It's just that the manufacturer says that you can reprogram individual bytes (normally for EEPROM) or sectors (normally for flash) without the memory cells/sectors being more damaged than that they can still correctly store your information.

With luck, and when used in a cool environment, you may be able to get several times more rewrites without failure. The figure they present is just based on statistical results. If used in extreme temperatures, the memory mail fail to correctly store your data after fewer operations.

The most problematic part is the erase, where you have to pump in a lot of energy into the memory cells. It is normally the time needed to pump up the erase voltages that represents the long erase times.