To limit the focus of the question, I'm going to say using Linux as the OS, and tar as the compression format. Clearly run-time is important, but knowing the archive is valid is more important. If providing a command-line, please also link to the documentation for it, and within your answer explain each segment of the command.
Aha! Found what we're looking for (Google saves the day)!
Like you, the author is looking for a good way to verify the TAR archive. He proposes a method to do just what you're looking for, and points to a piece of script software that does the checking for you.
It's not perfect, but it's better than nothing.
EDIT: It seems VeriTAR even supports compressed TAR archives.