That sounds plausible. Another idea: choose a section of "bad image" and a section of "good image" which should have similar colours and then generate mutations

That sounds plausible. Another idea: choose a section of "bad image" and a section of "good image" which should have similar colours and then generate mutations of the corrupted DCT square until you have a close match between the two areas.