A storage device includes storage circuitry and multiple memory cells. The memory cells are organized in multiple memory blocks of a nonvolatile memory. The storage circuitry is configured to define a partial verification scheme that specifies testing only a data portion of the data programmed to the memory blocks, to program data to a memory block, calculate redundancy data over the data, and save the calculated redundancy data in a dedicated memory, to verify that the data portion specified for the memory block in the partial verification scheme has been programmed successfully, to check a predefined condition for conditionally performing full verification to the memory block, when the predefined condition is fulfilled, to verify that data programmed to the memory block and not tested using the partial verification scheme has been programmed successfully, and to recover, using the redundancy data, at least part of the data programmed that failed verification.