Techniques for recovery of partially programmed blocks in non-volatile storage are disclosed. After programming memory cells in an open region of a partially programmed block, a fail bit count with respect to programming the memory cells is performed. If the fail bit count is above a threshold, then a recovery operation is performed of other memory cells in the partially programmed block. The recovery operation (such as erase) may remove charges that are trapped in the tunnel dielectric of memory cells in the open region of the partially programmed block. Note that this erase operation may be performed on memory cells in the open region that are already erased. The erase operation may remove trapped charges from the tunnel dielectric. In a sense, this “resets” the memory cells. Thus, the memory cells can now be programmed more effectively. Both programming and date retention may be improved.