I had my first ever chicken katsu curry in Japan in 2002 and that was the first time I'd ever had edamame too. We bought a load of golden curry from the supermarket there so that we could make Katsu curry at home. We then could only get it from the Japan centre in London until finally Waitrose started stocking it. I used to get frozen edamame from an Asian supermarket near Edgware as I couldn't find it anywhere else. Wagamama was the only other place we could get it then.
First time I had Prosecco was in Venice in 2003 - we came home and tried to find it in the supermarket here. Then it was suddenly everywhere.
Also discovered Cremant on a wine tasting tour in Beaun in France and brought two crates home with us - now alway buy that rather than Prosecco.
Orange pie from Corfu - found a recipe and made my own when we came home but thankfully they now sell it in Lidl during Greek week.