Hmm, Gallup does have quite a lot of information on numerous figures, going back a while (though often not far enough for my questions).
A lot of those name recognition numbers seem suspiciously high to me, I suspect a lot of people don't want to look ignorant, or feel obligated to give an opinion on everyone. Had a majority of Americans really heard of say, Ted Cruz in June 2013? I imagine a large amount of the "No Opinion"s are really "Never heard of", and a fair number of the approvals/disapprovals are just guesses on what they imagine a Senator from Texas to be like (generally, Republicans picking favourable, Democrats picking unfavourable). I agree, but I think 89% of voters having "an opinion" of Trump in Sept. 1999 means that his "true name recognition" was presumably still higher than 50%, even if not as high as 89%.
There is of course the possibility of name recognition going down over time in some cases. E.g., Donald Trump flirts with a presidential campaign in 1999, then drops out and his name recognition goes down for a while when he's out of the news. Same with, say, Al Gore and his 1988 presidential campaign. He makes a brief splash in 1988, then drops out of the news and some people forget he exists, so that the day before he's picked as VP his name recognition is lower than it was in 1988.
There's also a distinction between "name recognition" in the sense of "I've heard this guy's name in the news and have a vague sense of what news story his name is connected to" and real knowledge of who a person is. Cruz was in the headlines in 2013 over the budget battles in Congress, and I'm sure many people had seen his name in that context, but if you asked them cold without any supporting information "Who is Ted Cruz?" they wouldn't have been able to answer.
