Sounds like it may be a firewall issue or DNS issue. On the exchange server you can open a cmd window, type in nslookup
You should get a response like:
mx1.mail.yahoo.com internet address = xxxxxxxxxx
Then I would (in the same cmd window) type in:
c:> telnet mx1.mail.yahoo.com 25
This should connect to yahoo’s mail server on the SMTP port. If this works, then DNS and SMTP work.
I would check the queue properties for more information at this point.
If it does not work and there are no firewall issues connecting to these servers, you can (in a cmd windows) run the following:
c:> tracert mx1.mail.yahoo.com
You should see the trace route, this will tell you where you are getting hung up.