If parts of the files were overwritten before recovery, the likelihood is that those parts of the files are corrupted beyond redemption. If you are sure that the drive containing the video files wasn't written to following deletion of them, try a different method of recovery. I have used "getdataback" and "recovermyfiles" with reasonable success before.
Or, try playing the corrupted recovered files with GOM Player, which can play corrupted/partial video files:
http://www.gomplayer.com/download.html