It sounds like what you want to do is:
mplayer -vo null -ao null input.file
and then parse the output and return value to see if it could actually play & decode the stream. This will take some time (but be faster than realtime). If you want something even faster, here are some more suggestions:
One easy thing is going to be to do an
mplayer -identify -vo null -ao null
on the file, and then parse the output and look at the return value for something that looks reasonable.
With respect to the checksums being incorrect, it's going to be hard to know if this is an issue for your media player or not (mplayer, vlc, totem, etc.). A good media player will tolerate many bit or byte level errors with little impact on the resulting playback. A very strict media player will exit when it sees malformed or incorrect codec & wrapper bytes.
To verify the wrapper (container) bytes, you could do something like
mencoder -ovc copy -oac copy input.file -o output.file
The problem is that mencoder will want to create an .avi file for output. If your inputs are .avi, then this will work great.
You can run a similar ffmpeg commandline, like this:
ffmpeg -acodec copy -vcodec copy input.file output.file
If the files are .mp4 files, you might want to take a look at mp4box ( http://www.videohelp.com/tools/mp4box ) for doing a similar task. The matroska tools are also good for this kind of thing. ( http://www.matroska.org/ )