A method begins by detecting a recovery error when decoding a seemingly valid threshold number of existing encoded data slice. The method continues by sending a notice of the recovery error and a known integrity check value for the data segment to a rebuild module. The method continues by the rebuild module retrieving the set of existing encoded data slices and selectively decoding a different combination of a decode threshold number of existing encoded data slices of the set of existing encoded data slices until the data segment is successfully recovered. The method continues by dispersed storage error encoding the successfully recovered data segment to produce a set of new encoded data slices. The method continues by comparing the seemingly valid encoded data slices with corresponding new encoded data slices on an encoded data slice by encoded data slice basis to identify a corrupted encoded data slice.