We know that when Marty changed the future by stopping his mother and father from meeting he did not immediately disappear from existence. The photograph of his siblings began to slowly fade, and he himself only began to fade out of existence when his father almost failed to stand up to a bully on the dance floor, which really would have been the last chance to put history back the way it was (that his parents fell in love at that dance).
As long as Marty remained in 1955, there was a chance that he could put things right, and the deadline for that was the dance (the lightning storm was a secondary deadline for him to be able to return to 1985). It is fair to say then that the closer he got to that deadline, his chances of success lessened too. This could explain the slow fade of the photograph towards that time.
You may be right that when something is changed for certain then it immediately changes the timeline and things correct themselves - this was the case in the sequel Back to the Future 2 when the newspaper headline saying Doc Brown had been "committed" changed before his eyes to "commended". And of course, once his parents kissed and fell in love the fading photograph of Marty's family immediately restored, as did his strength. So I can see why you would think that having knocked down the pine the moment Marty arrived in 1955 should mean that detail was instantly corrected.
Really though, the same rule applies to the recording as the photograph, because as long as Marty remained in 1955 with the time machine he had the ability to go to any point in the past or the future - something he demonstrated by changing the time circuit to go back earlier than agreed and save the Doc. He could have, amongst other things, gone back and stopped the tree being run over. As long as that remained a possibility then there is no reason for anything related to the "Twin Pines Mall" to immediately disappear from existence. That future only became a certainty when he left the past and travelled forwards to his new future.
Remember also that the recording of Doc in the mall parking lot was filmed by Marty. Had his parents not fallen in love then Marty would never have been born and he would not have been able to make the recording of Doc Brown in the first place. This is something of a paradox but only proves that the recording is subject to the same "rules" governing time travel as the photograph. Had Marty's parents not fallen in love, the whole recording should have disappeared, not just change the name of the mall.
Further, consider what Doc Brown explained about timelines in Back to the Future 2. He stated that whenever something is changed at a fixed point in time, a new branch of time is created. We know that Marty changed his own history by the fact that, when he travelled forwards to 1985 from that point, various things were different - the demeanour of his parents and siblings, and of course the name of the mall. The recording in question is from the previous timeline, as was the photograph of his siblings. Although the fading of the photograph and its immediate restoration denoted the fading possibility that he and his siblings would ever exist, the photo was restored as it was. His siblings in the photograph were still wearing the same sloppy clothing from the old timeline and did not have the modified image that we see they have in the altered 1985. Arguably then, the recording would have been subject to the same rule - it may have begun to fade as the possibility of it happening lessened, but it may have been restored as it was when the future was fixed. It could be argued then that the future altered timeline that included the new name for the mall only became a certainty for Marty once he travelled forward in time to 1985.