Thanks Steph,
You were right, my work emails were not getting out of WordPress. The emails going to a POP servers (hotmail, gmail etc..) were making it out, those going to an exchange server were not. The solution for me was to install Cimy Swift SMTP (I am sure that WP Mail SMTP would work too). I upgraded to the Pro version. Thanks for the cool tool and the help!
For those who are using NetworkSolutions as a host, here is what I did to make it work:
1) Set up an email account in NS for my client (example: admin@yourdomain.com)
2) Sender name: (enter what ever you want here)
3) Sender e-mail: (use the email accoutn that I just set – admin@yourdomain.coml)
4) Always overwrite the sender: (left this unchecked…not sure what it does)
5) SMTP server address: (SMTP.YOURDOMAIN.COM.NETSOLMAIL.NET)
6) Username: (use email address you set up in step 1 – admin@yourdomain.com)
7) Passoword: (use the password you set up for this email box)
8) Use SSL or TLS?: (SSL)
That worked for me! Hope this helps someone else.