Probably this is because the Veil was reset along with the castle.
After each time the Doctor 'confesses', the Veil freezes and the castle resets, before the Veil also resets and begins to come after him again. At the very end of the cycle, after the Veil kills the Doctor, it disappears entirely - and yet we know that it must reappear to begin following the new version of him after he returns to the teleporter room and is reborn.
In fact, this question is answered in the episode's very first words (emphasis mine):
As you come into this world, something else is also born. You begin your life, and it begins a journey towards you. It moves slowly, but it never stops. Wherever you go, whatever path you take, it will follow. Never faster, never slower, always coming. You will run. It will walk. You will rest. It will not. One day, you will linger in the same place too long. You will sit too still or sleep too deep, and when, too late, you rise to go, you will notice a second shadow next to yours. Your life will then be over.
Each time a new version of the Doctor appears in the teleporter chamber, a new version of the Veil also comes into existence to follow him, hear his confessions, and ultimately kill him and disappear itself.
TL;DR: the Veil is reborn all those billions of times along with the Doctor.