Ok all, I may have the answer that will help at least some of you. I had the same issue with the registration email never getting to our users, so I contacted our host and ran the scenario past them. I received a fast reply and the instructions that would hopefully take care of the problem. "It worked perfectly!" Here's a copy of the message:
The server housing your account currently has phpmail() disabled. This is how WordPress tries to send mail. Below are instructions for a plugin you can install/configure to route around this for WordPress.
For WordPress 2.1 and up:
Please download the plugin from http://v-nessa.net/imh_files/wp-phpmailer.zip and follow the instructions below.
For WordPress versions below 2.1:
1) Download the plugin from http://www.v-nessa.net/imh_files/ShiftThis_SMTP-Wordpress_Plugin_v092beta.zip
2) Once the file is downloaded, unzip the archive and upload the shiftthis-smtp folder into the .../wp-content/plugins directory of the WordPress installation.
3) Next, log in as the administrator (usually yourdomain.com/your_path_to_wp_installation/wp-admin
4) Go to Plugins and select ShiftThis SMTP Swift Emailer, and Activate the plugin
5) Go back up to Options ~> SMTP and modify the email settings:
Server Address: localhost
Username: outgoing server account name (must be a complete email address you create in cpanel)
Password: outgoing server account password (password for above email address)
Use SSL or TLS? No
Port: 25 (Default SMTP Port)
You can set the outgoing server to use SSL, but as with any other email client, you must use port 465
Like I said, the plugin did the trick for me (I'm using v2.3.1, so I had to do a little extra figuring on settings) . Hope it helps you too. If it does, hopefully someone will add the link from this post to some of the many other messages that seem to say basically the same thing.