We can not begin with the past simple and continue with the past perfect, right ? I think, we can, you did it in #1.
But we may begin with the past perfect and go on with the past simple as in (Usually we do not start with the past perfect if we didn't refer to the past in previous sentence and want to tell that this action happened in the deep past before either the action or event which happened in the past.)
1. "He told me he'd been to many countries, having visited different towns and seen many people."??? Here you started with the simple past (he told me). I think we usually start with the simple past and use the past perfect if need be, only. (If we should mention that some action happened in the deep past. You continued with the past perfect what is correct and also you should have used the perfect participle "having visited and seen")
"It had been a long time since I last saw her,(.) (in my opinion this is not correct, "I last had seen her" must have been used as a correct adverb of time for the first clause because the past perfect refers to the deep past and the simple past tense doesn't.)and If someone hadn't mentioned her name I think I would have hardly recognized her." There is a chance that someone might have said that because when we speak we can't construct our phrases completely in advance.???I don't understand this final sentence