Mail issues making my head spin

Another possibility could be a badly configured sender address. Are you sending mail from the same domain as your Discourse hostname? If not, then did you change the notification email address?