I seem to remember it being on the 1995 VHS. Are you sure?
This was absolutely a 2004 change. It was jarring to see it for the first time on DVD if you knew the movie like the back of your hand as I did at the time.
You also have to keep in mind, most of the major visual effects changes from 1997 and onward came in waves. They didn’t just go in and change 1 random thing here or there every few years, there was a whole new set of changes that usually came with the introduction of the films appearing on a new video format.