The outbound mail servers used by Godaddy hosting customers appear to be blacklisted by the Abusive Hosts Blocking List (AHBL). Over in this Godaddy Community Forums thread, a Godaddy representative named ChrisG seems to be implying to complaining clients that AHBL is unreliable: "We strongly recommend using consistently reliable block listing services such as Spamhaus.org. You would want to contact the ISP/Email provider and insist that they do not use AHBL's listings as legitimate emails being sent to you are being denied because of their listing."
Nearly everyone who has been blacklisted complains that the listing is unfair and that the blacklist is unreliable. Sometimes that's true, sometimes not. My experiences with the folks behind AHBL have been near universally positive -- and my experiences with Godaddy's abuse desk have not been so positive. So, I do suspect that perhaps AHBL is in the right here. If so, Godaddy needs to step up and directly engage with AHBL, and figure out what needs to be done to resolve the issue to AHBL's satisfaction.
Brielle from the AHBL responded in the thread with her take on events. She responds to Godaddy's claims that Godaddy continues to work with AHBL on the issue: "No, you are not working to resolve this issue. Last communication we had with GoDaddy was back in June or July, and were told they had no intention of 'resolving' this issue."
As it stands now, who really loses out here are Godaddy's clients -- finding themselves caught in a pissing match between a service provider and a blacklist publisher.