Let's throw away the entire fossil record. Let's remove Darwin and Wallace. Let's remove the theory of evolution from human consciousness until we discover DNA. Guess what, DNA is a record of evolution. We would've just recently discovered we evolved purely based on DNA alone. There are decaying genes, dormant genes, vestigial genes, and common genes. DNA proves evolution true. We don't need fossils at all.
Those gaps represent opportunities to make creationists eat their hats! The "tree of life" can be mapped out geographically. You can actually use the theory of evolution to accurately predict WHERE you will find the next "missing link"and WHAT it will look like.
What's more, you could be handed nothing more than the genetic material of every known creature without the labels and accurately reverse engineer the tree of life AND accurately determine WHERE the fossils were found.
Not only is the Law of Evolution internally consistent, it explains and predicts the biology we see in the real world. . . At worst, there is still debate about the particular pattern it took but the foundational principle, that life changes over time, is as rock solid as any other scientific law.
I'll say two things.
1) Around 99 % of all species that have lived are now extinct. Think of how many species are alive today. It's obvious that the fossil record wouldn't cover all species. (But, as mentioned by user Hippocrat, the missing link is a myth.)
2) No. 1 doesn't really even matter. The fossil record is a nice thing to have, but evolution could be proved without it as well. Many creationists seem to think that fossils are the only evidence for evolution, while it's really just the icing on the cake, the cherry on top. There's genetic evidence (it would take days to write down all the different forms of genetic evidence). There's comparative anatomy. There's observed natural selection. There's artificial selection. I could go on...
Obviously some fossils may never be discovered due to sheer chance, or they never formed. However, the missing link is a false question as if another link were to be found, people would just say where is the other missing link, if another was found again, people would still say where is the missing link. The question is designed so there are never enough fossils respites loads of other fossil evidence, along with with other evidence such as genetics. Imagine evolution a series of drawings that depict an action being performed, but some are missing, by observing the past and present drawings you can fill in the gaps.
To prove that something actually happened you have to be able to redo it. You cannot prove evolution this way. With statistics the chances of the big bang are one in a million, and evloving life is one in 1 trillion to have the amino acids from protiens to form a cell.
Fossils, dna, vistigal orgins, or anything else can't be proof that evolution is a fact. Historical science is fundamentaley diffrent from observational and expieramental science. Having a fossill or not having a fossill can prove nor disprove anything. A million contradicting infrences can be made about what happened to a fossill millions of years ago. There is no way to be 100% sure what happened to anything so long ago. Whether it was evolution or intelligent design you can't prove. It takes a bunch of guessing or faith
I do believe in Evolution but to claim that it is a fact, the problem lies with the term fact itself. It's more of a technical problem. Fact is something known by actual experience and since evolution is a process that occurs over many times any human's lifespan, scientific experiment is impossible. What we can do is to postulate and find evidence for it - the links were joined together to construct this theory of evolution by scientists, it could mean there are minor discrepancies here and there in reality but evolution is a close enough explanation but not a fact. But if you were to ask me whether I believe in the truth of this theory, I do.
P.S. As people have pointed out Fossil Record is not the only proof of evolution.