> The entire thing can be rebuilt and it will still be the real Notre Dame de Paris. It'd have to stop being used for the original function.
This is demonstrably wrong, as we have many examples of old buildings and we know what people actually feel about them.
Consider two very famous examples of buildings that completely changed their purpose, but are still the same building: the Pantheon and the Hagia Sophia in Istanbul. The Pantheon was a Roman temple to all of the Gods when it was built in 126, and became a Christian church ~400 years later, but everyone recognizes it as the same building. The Hagia Sophia was a Christian church built in 537, and 1100 years later became an Islamic mosque, but it is still the same building to everyone.
Then for the opposite example: St Peter's Basillica at the Vatican. This was built in 1506 on the site of a much older church, also called St Peter's Basillica (commissioned by emperor Constantine), which also served as a Christian church, was also used the parish of the Pope, was also the location of papal coronation and so on. And still, no one would say "St Peter's Basilica was built by Saint Constantine", because the current basilica is universally recognized as a new building, despite serving the same function.
A building is recognized for the beauty and specifics of its structural and painterly elements, not for its role. If it is destroyed and rebuilt in almost the same size and shape, then it is recognized as the same building; regardless of entirely changing its purpose.
Conversely, if a building is rebuilt into a completely different shape, even a universally admired as beautiful one, it is considered a different building, even if keeps serving the same purpose.