Oh. I believe that the first time it said “A New Hope” on the cover was for the 1995 Faces VHS Boxset release. And it wasn’t even on the actual cover, only on the sides. Before that it was only labeled as “Star Wars”.
here’s the faces boxset: 
Here’s what most US releases of Star Wars on VHS looked like: 