This is so disheartening to read. When it was first reported to Cox that only Cox customers can't send email to that (previously Cox hosted) domain, the SMTP server team should have sprung into action to quickly solve the problem. Through cursory system checks and/or parsing the server logs for a "test email" sent to that domain, the point of failure could be quickly identified and resolved soon thereafter. Your experience, unfortunately, is indicative of today's service provider failing to properly scale their support resources to properly and expeditiously meet the needs of the customer.
