I had a similar experience with en axchange box (actually exchange has nothing to do with it).
If your DNS provider does NOT have a reverse DNS, yahoo,hotmail, gmail WILL NOT WORK.
Go to DNSSTuuf.com to check you domain settings
GabrielComputer Technologies Group, Inc.225-293-2844
From: exchangelist-bounce@xxxxxxxxxxxxx [mailto:exchangelist-bounce@xxxxxxxxxxxxx] On Behalf Of Brian Pituley
Sent: Monday, October 08, 2007 10:14 AM
Subject: [ExchangeList] Re: Yahoo.com Email is blocked - New Installation
Can you send to any other, non-yahoo external accounts?Do you have rDNS records set up for your mail server in the outside world?Brian Pituley
Director of Information Technology
From: exchangelist-bounce@xxxxxxxxxxxxx [mailto:exchangelist-bounce@xxxxxxxxxxxxx] On Behalf Of john_gitzen_ii@xxxxxxxxxxxSent: Monday, October 08, 2007 4:09 AM
Subject: [ExchangeList] Yahoo.com Email is blocked - New Installation
Importance: HighHelp Listers,You may recall I posted a question titled ?Steps to install a new Server?. Well we put that server into production this weekend and now I get to fight the fires. In recent testing I discovered that emails going out to my yahoo.com email address are not being received, but emails sent to my charter.net email address are!?! Any suggestions on what I should look for? I looked in my DNS table and I see no problems. I have an external webhosting company ? acomhosting.com and we did have email going through their site, in fact my users still have the POP3 definition in their Outlook setup, but it is at the bottom below our Mailbox.Why one SMTP email client and not another?John
The information in this communication and any attachments is confidential and may be legally privileged. If you are not the intended recipient, any use, review, dissemination, distribution or copying of this information is strictly prohibited. If you have received this communication in error please notify us immediately and delete the original message and any copies of it.Any opinions, conclusions or other information in this message that do not relate to the official business of the company are neither given nor endorsed by the company.