I also want to thank ruthlessbookie. That plugin finally did the trick. This problem was driving me nuts.
I use Bluehost and will check with them per Andy’s suggestion above. But this must be an issue with a lot of folks. Is there a way to make sure it will work is a host doesn’t support smtp.