There are several ways of fixing/working around this. Some are mentioned in some posts and others in different posts. Depending on the setup, plugin, or whatever may be involved, it seems people have different results or preferences.
I will list a few of the common ways that have worked for me:
First is to change the way WordPress generates the headers:
1) You can modify wp-includes/class-phpmailer.php and change the following lines(around line875 if using WP 2.7):
$result .= $this->AddrAppend('From', $from);
to
$result .= $this->AddrAppend('From', $from);
$result .= $this->AddrAppend('Envelope-from', $from);
That should fix the problem, though it won't work for any plugins that don't use class-phpmailer.php
2) WordPress uses wordpress@domain.com as the default email address. You can either create and use this address, or you can download the following plugin which allows you to alternate the wordpress@ address to anything you want (@yourdomain.com)
http://wordpress.org/extend/plugins/wp-from-email/
3) You can install a plugin like(but not limited to): http://wordpress.org/extend/plugins/wp-mail-smtp/ and in the plug-in options tab set the options to:
send mail using SMTP,
send the mail using your new email address,
fill in the SMTP host, username and password that your host gave you when you set up the new email address,
YES, use smtp authentication. (Yes, I'm aware this method doesn't actually change the headers, but most people don't bother with them anyway)
These are some common ways to fix the WordPress email woes. Hope it helps
shiner_man
thomasw98
bh_WP_fan
vinayy