Do DNA footprints vanish in generations?
You seem to be figuring that since $A_1$ has half the genes of $A_0$, and $A_2$ has half the genes of $A_1$, etc throughout the generations, we quickly get to a point where $A_n$ has none of the genes $A_0$ had.

This would be correct, if we assumed no inbreeding among the descendants. And by "inbreeding" I don't mean siblings or first-degree cousins breeding, but any of $A_0$'s $n^{th}$ descendants breeding with another. Which is clearly absurd; at some point you're going to run out of breeding partners who aren't also a descendant of $A_0$, unless the lineage isn't very prolific and the number of descendants $A_0$ has is always a small proportion of the total population. And in that case, sure, those genes are probably going extinct.

The same thing happens the other way around by the way; we (most of us) have two grandparents, four great-grandparents, etc. As we go back in time this exponential growth quickly outstrips the amount of humans that were alive at the time our $n^{th}$ great-grandparents were around. That's because that exponential growth assumes no inbreeding, which there is. There is a point in time in the past beyond which everybody alive today is the descendant of everybody back then who has any descendant at all; that's called the Identical Ancestors Point. See for example:  

https://www.nature.com/news/2004/040929/full/news040927-10.html

The end result is that there are really two outcomes for $A_0$'s descendance: either they increase over the long term faster that the overall population grows, or they increase at the same rate or slower. In the first case, we'll reach a point where the whole population is part of $A_0$'s descendance. In the second, unless population growth is huge then $A_0$'s line is probably going extinct. Even if not, and if we assume individuals are breeding randomly throughout the population (not a good assumption, but no gene dilution without it), then the original assumption that $A_0$'s descendants have fewer and fewer of $A_0$'s genes every generation is correct, and $A_0$'s genes will likely go extinct even if their descendants don't.

On the other hand if $A_0$'s descendance end up consisting of the whole population, then no more "dilution" can occur. Say at that point every individual has 1% of $A_0$'s alleles; their offspring will also have 1% of $A_0$'s alleles on average, and same goes for all later generations.

Note that at that point $A_0$'s alleles are distributed throughout the population; even if everyone has 1% of them, they don't all have the same 1%. So the question of whether "what makes $A_0$ unique" is present in the descendants is really hard to interpret. Some of $A_0$'s alleles may be present in everybody at that point (they have become fixed in the population), some may be present in X% of the population, some may have gone extinct. The specific combination of alleles that made $A_0$ is gone, but then it was gone when $A_0$ died. As for the question of whether scientists can investigate the descendants and find traces of $A_0$ after all those generations, the answer is "sure": see the aforelinkedto nature article.

More to the point, consider this sentence you wrote:


  Obviously if $A_0$ is human and $A_n$ is human then they share a great deal of their genes with one another (something like $99.99\%$)  


Do you not see how this factoid relates to your question? You are asking whether human $A_n$ still shares some genes with its ancestor human $A_0$, and caveat that "obviously" they already share most of their genes, what with being human. You mean, what with both descending from the common ancestor to all humans. That those $99.99\%$ of identical genes come from. Except of course that not even, given $99.99\%$ of that $99.99\%$ comes from our common ancestors with chimpanzees, and so on. Most of "what made the common ancestor to all life unique" is still in our genes today! So yeah, it will take more than a human-scale $n$ generations for all traces of a human ancestor to be predictably erased from its human descendants (keyword "predictably"; in practice many lineages and alleles do go extinct, but not all do and you can't really tell which in advance). More than that, on those evolutionary timescales natural selection is a strong force and you get phenomena like conserved genes - that is, genes that are important to the organism and are thus selected for to stay the same. At that point there is no "random dilution" phenomenon happening: there are specific forces at work to maintain the gene in all descendants in a more-or-less unchanged state.