How many tapes is it? Are they all from the same source recording camera/VCR? Some tapes do not have a linear track, especially tapes made on home cameras.
The HR-S8500 is not one of the suggestions machines by this site. I believe that one is too old by one generation.
The Panasonic may be playing the HiFi track, even if it says otherwise. It depends how sophisticated the deck is. What's the full model number of that unit? It doesn't sound like a S-VHS VCR that has those kinds of options (linear only audio playback).
Cleaning heads rarely does anything.
And welcome to the site. You're in luck -- I just happened to be on the site when you posted.