This is only because Perot drove down Clinton's vote % in 92 and 96.
On the other hand, Clinton actually split the South with his Republican opponents. Obama carrying VA and FL (and NC, if we count 2008) is hardly comparable to this.
Also, Clinton certainly performed far better with White voters, especially in the Upper South.
Neither Virginia, North Carolina, nor Florida is truly Southern by political culture Even Texas is about as much Western and Midwestern as Southern (it is the "Midwestern" parts of Texas including Amarillo, Lubbock, Wichita Falls, Abilene, and Midland-Odessa that will make Texas a tough pick-up for any Democrat).