My solution was to move my client off of GoDaddy. I spent a week trying to resolve email issues with GoDaddy and came to the conclusion that their support has a minimal understanding of how email servers work.
Search any support forum and you'll find Godaddy mentioned often, whereas in most other issues the hosting company's name is rarely mentioned because they have standard setups.
GoDaddy registration - good, Goddady other services - not so much. Just my opinion. :)