Do you guys know if there are any programs available for checking the integrity of WMV, AVI and MPG files? An older HDD which stopped working a few months ago spins up again but the file system seems to be corrupt. However, I found a program for recovering files and the program recovered most of my recorded TV shows, but I am not sure if the files are in order (they do open in WMP).

afaik there is no way for such software to exist.

A video transcoder, and some video re-muxers, can tell you about errors in the video.

You could use FFMPEG to convert the video and audio to another format, or, if I recall correctly, to output it to a null file just so you can test the decoder part. If the decoder part of FFMPEG encounters an error it will log it to the screen. It's kind of hard to use though if you don't understand it beforehand. Their approach to documentation is "look at the source code to figure out what it does".
http://www.videohelp.com/tools/ffmpeg

I check integrity of MPEG-2 based video (TS, MPG, or VOB) using Videoredo, which is not free software. Re-muxing it also checks for broken parts of the audio or video and re-syncs it, telling me about the errors at the end and the length of the final video. This is mostly limited to errors in sync due to missing or wrong timestamps.