What is your setting for "Email Transport" in Admin->Configuration->Email Options?

if it's "sendmail", try changing to "sendmail -f"
if it's SMTP, try changing to SMTPAUTH

This will cause the email to be sent from "your" hosting account, instead of from the server in general (which usually sends as "nobody" or "anonymous" or "webserver", etc). If it's sent from a generic address, some servers will reject it as potential spam rather than send it.