I probably saw A New Hope five times in the theaters in '77 and '78; the scene in question was never in the film when I saw it back then. I also remember seeing the movie a lot when it first was shown on cable TV (1983 or so), and neither that scene, nor any of the other deleted scenes, were in it – it was the same as the original theatrical release.
That said, I’ll note that:
- The scene was in the novelization which was also issued in 1977 (and may have been in the comic book adaptation, as well)
- Images from that deleted scene have been around since then, too. (Edit: see @Horatius 's link, which includes images from the Star Wars Storybook)
- An adapted version of the scene (along with many other additional scenes) was included in the radio drama adaptation of the film, which first ran on NPR in the U.S. in 1981. (I added this to the list just as @erysichthon made their post below)
- Video clips of it have been out there since the '90s, if not before – I have a CD-ROM from LucasArts, from around 1998, called “Star Wars: Behind the Magic,” which has that scene, among other deleted scenes, on it.
I’m going to ascribe it to the Mandela Effect.