I don’t have a good feel for it, but I’d say early 1990s. I’m not really looking for the first letterbox formatted VHS, but when “special letterbox” editions started popping up with some regularity (usually for something that had already been on the market for years in “TV format”).
Around the mid-90s I would say. I think I bought my original Star Wars trilogy letterbox VHSes around 1996.