Alhamdullillah after days (and I mean literally days because each day I can spend only a few minutes on this problem) I have finally got it working. To set up postfix to use relay with authentication, just ask the oracle. But to get it working with godaddy? I finally gave up and sent them an email. And in their reply was my answer:
Username: Your full email address (i.e. firstname.lastname@example.org)
Outgoing Mail Server: smtpout.secureserver.net
Outgoing Mail Server Port: 25, 80, or 3535.
And so first I tested the ports. After telneting the host and ports I finally decided that most probably would work best because the server response has the word 'auth' in it (I have no idea whether it's even relevant or not). Anyhow changed it my /etc/postfix/main.cf to use the 3535 port:
relayhost = smtpout.secureserver.net:3535
And the most important part is the username. It is email@example.com. It is the firstname.lastname@example.org you registered your free mailbox with. Not your login name to godaddy. Use the email address. And then run postmap, restart postfix, and viola, it is sending mail and those mails don't just get dumped into trash. Fuh...