Depends on the format, for example PNG has checksums per segment which make it extremely easy to find if the segment has been correctly rebuilt. Same goes for ZIP and RAR, and JPEGs can be matched against the Huffman tables for invalid byte sequences.

Also for JPEG there was a (sort of experimental) carver that validated the image against the thumbnail, and then decided if it was correctly reconstructed or not (and maybe it also helped to choose the correct block when there was an error). Still, most of this tools never left the alpha stage, and ended as curiositys presented in a conference and then left to rot.

Yes :), it is queer how some programs/tools that should exist and of which we do have the basic algorithms were never properly written/developed while we have tens or hundreds of tools similar among them missing these functionalities. Another kind of tool that was never properly developed is interactive jpeg repair, besides the good jpegsnoop: http://www.impulseadventure.com/photo/jpeg-snoop.html (which has only some of these functionalities) there are a handful of tools that are of little or "very narrow" use, but nothing much effective at rebuilding a damaged jpeg.

I've seen this in the steganography/steganalysis "community": almost every time a script or program is written, its purpose is to rapidly fix the needs by some highly specialized expert who deems that development too simple (that is, to himself) to further develop into a full-fledged tool.