I've done some Googling for you all.
It seems that GoDaddy have the following rules from what I've found:
1/ The "From:" email address CANNOT be a gmail, yahoo, hotmail, aol, msn etc email address - if it is then the email will get dropped as spam.
2/ The "From:" email address is best set up as an address on the same domain as your sire - so if your blog is http://www.example.com you need an address like email@example.com
3/ The "firstname.lastname@example.org" email address given in the example above MUST actually exist on your domain. You may need to create this email.
4/ You can only send to 250 or 1,000 different email addresses in 24 hours, any more unique addresses than that will be blocked. (I've quoted 2 numbers as I've found references to both - the lower seems more recent too)
5/ PHP mail() function is totally unsupported on Windows IIS hosting, you must be on Linux.
6/ It may be worth channeling your emails via the relay-hosting.secureserver.net server using something like the SMTP Mailer plugin.