Southerners commit adultery more often than thier Northern counterparts.
You may be right about that, but they still a lot less likely to vote for someone who does it, or supports it. I believe that by 2000, enough southerners had not moved on from the Lewinsky thing to cost Gore the electoral votes of all the southern states that had voted for Clinton. There was no other objective reason for those states to flip from 1996 to 2000.
And Clinton left the presidency with very low personal approval ratings. That doesn't imply that people moved on; they simply compartmentalized to some degree personal conduct from performance in office. Southerners were less likely to compartmentalize.