Wow, okay, so mystery solved!

So here's what worked for me:

Admin>Config>E-mail Options>E-Mail Transport Method? sendmail-f
SMTP Email Mail Host smtpout.secureserver.net
SMTP Email Mail Server Port 3535

And in the GoDaddy cPanel, go to Email>MX Entry>change from Local Mail Exchanger to Remote Mail Exchanger

That's it.

Thank you, DrByte, for your help!