I was a paralegal in North Carolina for 6 years, and am now an attorney in South Carolina, so I have been dealing with clients in the mid-south for a while now. A lot of my correspondence is by email, and my general rule with emails is that if the client signs their email FirstName LastName I respond to Mr/Mrs/Miss LastName, but if they sign FirstName only then I respond to FirstName. If we aren't corresponding by email then I call the client Mr/Mrs/Miss LastName until they explicitly invite me to call them FirstName, or there is some other indication that that is their preference (some clients will not outright request a first name basis, but our relationship will otherwise indicate that a first name basis is appropriate). As a PP has already mentioned, first names are used between attorneys, and there are some other professionals I will also default to first name usage with; for instance, I am a volunteer guardian ad litem, and use first names with DSS caseworkers.
I don't use "Ms.", if I don't know a woman's marital status I refer to her as "Miss". This began at the direction of my previous boss, who told me that some southern women would take offense to "Miss". I was raised in Maine, and there "Ms." was common. After my boss directed me to use "Miss" rather than "Ms." I started to pay attention to what others were doing; I found that in NC and SC I was/am called "Miss LastName", but when I lived just outside of DC for 2 years (between living in NC and SC), I was called "Ms. LastName".