Experts say, rather than do a verify, simply prove the backup is a good one completely by restoring it, where if the restore is successful, you've proved the backup is a good one.  Places I have worked, we have never seen a failure on the verify if it was in place.  In fact, I even read where some people have even experienced a good verify of the backup and later found their backup was not a good one after all when trying to restore it.