Re: "If someone wanted to draw its family tree over the last 1000 years, he'd write a binary tree with a depth of about 40..."
No one would attempt to draw a tree of that depth. I appreciate that this is a theoretical exercise since there are no cases that I know of where anyone would claim a full genealogical history over that span. Some "royal" households may claim to be able to trace back a specific line that far but that's not a complete genealogy as many partners' lines will have been excluded.
As you say yourself, the depth of the tree is approximately Depth = Int(TimeSpan/Generation), or 1000/25 = 40 in your example. An equivalent binary tree would have 2(Depth+1)-1 people, or 241-1 (about 2,200,000,000,000) in your example, which is simply an unmanageable number. It would also be ignoring all siblings but that's because it would be a pedigree chart rather than a family tree.
There would certainly be a lot of pedigree collapse, and this might be far more common than one might expect. Our ancestors would have been part of communities - villages, hamlets, tribes, towns, etc - and this would increase the prospect of shared ancestors. Remember too that some religious communities strive to share ancestors and cultural heritage by deliberately marrying within their own community.
Although someone might draw their lineage as a tree (whether as a 'family tree' or a 'pedigree chart'), the internal relationships do not form a "tree" in mathematical terms. This is an important consideration for software designers since you don't want to be represented twice (with independent details), or end up being your own ancestor. Again, in mathematical terms, those relationships form something called a Directed Acyclic Graph, or DAG. This is more general than a simple (mathematical-)tree but still has rigid constraints, in contrast to a network where virtually any connections are deemed valid.