I forget exactly where you're at, but how about US127 to TN28 in Dunlap, which avoids the traffic mess in Chattanooga? Then take US72 west, AL279, AL79 in Scottsboro, AL160 in Cleveland, then take it to I-65 south.
You'll trim off 40 miles from the drive, but add about an hour. Looking at your county map on mob-rule, it doesn't look as if you'd gain any new counties, but it will free up mileage for spinbacks or picking up a few counties here or there.
Natchez Trace Parkway clips a bunch of counties in central and northeast Mississippi; not sure how specific your county-counting rules are, but I think that's going to be too far out of the way.
You'd pick up a few in SE MS with MS63 - MS57 - US45 to Meridian, which is all four lanes and rather sparse on traffic. Continuing on US45 north of Meridian is also four lanes, but might be out of your way (it's also annoyingly bumpy).