Who is your webhost? I ran into a similar problem and I found a SMTP plugin for wordpress. You have to setup an email address that supports POP and get the server name, username, and password to the email address inbox. I think this is the one that i used before: Easy WP SMTP. It works with Gmail, Windows Live, etc.