I have French and Canadian citizenship. Back in 2012, after a J-1 internship visa in NYC (under my French citizenship), I left the USA and went to Montreal before the end of my J-1. I then tried to get back in the US by bus purely for tourism purposes, and to my surprise the border agent denied my entry. His reason: I hadn't gone back to my residency country (which was France). And so they assumed that I was trying to settle as an illegal alien in US territory (I wasn't of course, and my plane back to France was leaving from NYC a month later, but I didn't have the reservation on me since I had no idea I was even doing anything suspicious.)
Finally, I stayed a month in Montreal, and went back to the US border (by bus) with my plane ticket leaving from NYC, and proof I had an appartement waiting for me in France (rent, gas bills, etc.). I pleaded them to let me get my plane, and they let me in, under the mandatory condition that I take my plane back to France (which I of course did).
Since then, I've been living and working in France. I have been back to the USA twice: once with another J-1 visa for another internship, and a couple of years later as a tourist.
The thing is: every time I've been back, despite having a J-1 visa or ESTA from the embassy, I've been put in the "back room" at the border, where a border agents asks you a lot of questions for quite a while. It's quite nerve racking, as every single time, I'm not sure I'll actually get in the USA.
This is even more problematic nowadays, as my current job in France will soon have me travelling to the US for business reasons. And missing a business deal because of an honest mistake I made in my early 20's would be quite a problem.
My question is this: Will this border denial in 2012 be permanent in my travel history/record? Is it possible to clean out this record? Is there a chance that it gets clean after a certain number of years? Or will I always be put in the "back room" for questioning for the rest of my life every time I try to enter the USA?
PS: I have NO criminal record. .