I had given up on doing this, but ended up seeing all the good suggestions on this thread and thought I'd give it another go yesterday and quickly succeeded.

The problem with GoDaddy's SMTP server is two fold:
1/It won't send an email that originates FROM a lot of common domains (e.g.: @yahoo.com, @gmail.com, @hotmail.com but also some more random ones)
2/But it won't send emails TO pretty much anything but the domain on which the site is hosted either.

Number 2 is easier to deal with an was explained in this thread, so I'll start with that. (why didn't I call that number 1 you ask? I dunno).
The trick is simply to create a redirect address on the GoDaddy control panel and redirect it to whatever you want, even hotmail, yahoo, etc. (Note that "normal" addresses with or without a CC work too).
And if you send your email form to that address, it will work fine!

Number 1 is fairly easy to deal with too if you know why it wasn't working.
Some submission would go through and others wouldn't depending on the submitter's email address.
So simply put the "From" field in static in you PHP page to something like "noreply@yourdomain.com" (yourdomain.com being the one that you have on GoDaddy).
The email address that the submitter entered can easily then be inserted in the body of the email.

For bonus points, I thought I'd try to change the Reply-To field so the people who receive the submitted form can hit reply on an email received from noreply@yourdomain.com, and automatically reply to the address that the submitter had typed.
This can be done in your PHP file like so:

$email->addCustomHeader('Reply-To', 'heidi@sitename.com'); 

$email = new Email("noreply@yourdomain.com", $To, $Subject); 

There you have it!
I have finally managed to get a stupid email form working on GoDaddy.
Would you believe they originally called me (after I complained by email) and made me do all sort of stupid shit, trying to prove that my code was wrong?
I actually asked what were the restrictions on sending to and from, but they had no idea.

Well, I hope this helps someone else in the future.

Thanks to everyone who got involved.

JuLo

Hi Julo,

can you explain how to seup redirect address on godaddy? the only email i can not send to right now is to hotmail users.