Since this question hasn't been closed, here's a guess as to what is going on.
Laura Wattenberg of BabyNameWizard.com, apparently a widely quoted authority of the subject of American baby names, points out that fewer babies share the same name now than fifty years ago. At the start of the baby boom, over 40 percent of babies born had one of the 20 most popular names in the country, mostly English names of saints: John, Mary, Christopher, Elizabeth, Michael, and so on.
According to the Social Security Administration baby names website, Steven appears in the top 20 list of names for boys born in the United States from 1949 to 1976. In 1961, almost 1.5% of all boys born in the U.S. were named Steven. Stephen was likewise very popular, peaking at #19 for boys born 1949–51. Plain Steve is rarer, but breaks into the top 50 from 1957 to 1963.
Since its postwar heydey, the name has seen a steep drop-off.

("NameVoyager" chart from BabyNameWizard.com, based on Social Security Administration data, hence the huge surge after the 1930s).
That isn't because the name has gained any negative associations, at least more than any other name, but because there is a much wider diversity of baby names now thanks to a combination of factors from mass immigration to a cultural preference for uniqueness. It isn't just Steven; there are proportionally fewer Roberts and Williams and more Jaylens and Trigs.
While Steven has undergone a secular decline, more exotic variants have been climbing the charts:

Note the y-axis and don't draw the wrong conclusion here; Steven is still orders of magnitude more popular than Stefan for newborn American boys. But you can see that it rises from almost total obscurity to something popular enough that the average person might encounter it. Stephan similarly shows a meteoric rise, peaking in the 1980s.
In 1960, Stephen would probably have been accepted as a variant of Steven, whose pronunciation is unambiguous, as might Kathryn for Catherine. By 2010, there are proportionally fewer Stevens and Stephens out and about, proportionally more Stephans and Stefans, and greater awareness of the latter pronunciation thanks to the Internet, if nothing else from clips of Steve Urkel's alter-ego Stefan Urquelle being shared nostalgically.
Possibly, these effects are exaggerated in the South, or possibly it's some other factor, like maybe Southerners are more— or less— likely to address you by name than people in other parts of the country, so you notice it more. I also doubt that 2012 represents any kind of cutoff, and unless we have actual evidence that usage changed around that time, it's probably just the first time you noticed a trend that had been growing for decades.
It's been a while since worked with a group of 350 that included 16 Stephens and a Stephanie so that those people had no problem hardly seems relevant - and to my ear reading either as Stefan would be easy way of announcing yourself as a non-native speaker.
Could "Almost Everyone" or "80%" of the time "since around 2012" mean you keep meeting Central or East Europeans?
– Robbie Goodwin Jul 23 '18 at 20:27