The solution for this should be SPF record or if that doesn't work smtp issue.
SPF record example: v=spf1 a mx ip4:xxx.xxx.xxx.xxx -all
replace the highlighted area with the website ip address - then add underlined record example to client's DNS records as a TXT record.
Alternatively, you can go into their cPanel account, under Email > Email Deliverability, you'll find the DKIM and SPF records there. Copy them over into their DNS records as TXT records, copying the Name and Value.
more info.
Type=TXT | Host=@ | TXT Value="underline example above" | TTL=custom | Seconds=600 (if the dns provider allows 600, if not you will need to test the time until it allows you to save.)
This should fix the problem however, if it doesn't want to play nice try an SMPT plugin for WordPress sites, if not using WordPress this will need to be done on the server level.
Note. This is a common issue with cheap shared hosting like Godaddy. Probably because there is a spammer on the same IP. Also, GoDaddy states that with their servers, SMTP doesn't work that well, so they recommend using the PHP Mailer settings.
Sincerely,
Your Friend,
Sir Doogie Houser.