My email to the CEO worked like a charm. I received a call first thing this morning from a representative of the office of the CEO. By the time he called me, he had already cleared the charge and applied additional credit towards the next month's bill. He spoke to me at some length about the firm's recognition of issues with the shipping system and the way the non-returned charge was being applied, and efforts they are undertaking to address the issue. He pointed out that, since I received an X on release date, I was one of the early customers with this returns processing problem, and that's why it took some time for AT&T to recognize the problems on their end and help me out. He said new cases like this are rare now because they have better determined the problem and what is needed to fix it. They are having some problems with USPS communications that they are trying to resolve with them. They also had an error in their system regarding the amount charged to customers for non-returned devices (charging for the value of an iPhone X rather than the value of the trade-in) which they have since fixed.
He listened to my concerns and was very apologetic. He encouraged me to try Next again in the fall when I upgrade (assuming I do), claiming that they are getting the problems worked out.
I'm glad to finally report that my issue with the trade-in is fully resolved. I hope they work on support staff training so that we don't have to escalate it to the CEO office in the future.
If you are having major problems getting your case resolved, I highly suggest emailing the CEO. Make sure to give them as much detail as you can and attach any relevant evidence to your email.