When I send mail from an outside domain, it's not coming to my company's domain. When I do send mail from my domain to another domain, it works, but not in Yahoo. I have tested SMTP and DNS configuration by using smtpdiag.exe file and it is all working OK.
I recommend you use a machine outside your company to check your public DNS record. Specifically, have a look at the MX records, and test telnetting to port 25 for each of these records (use the IP addresses associated with each hostname). I suspect that at least one of your MX records is not correct or is missing, and therefore internet SMTP clients can't find your domain.
Do you have comments on this Ask the Expert Q&A? Let us know.
Related information from the TechTarget Windows Network:
SearchExchange.com Tip: Common Exchange mail delivery issues
SearchExchange.com Reference Center: DNS
SearchWin2000.com DNS Primer: Understanding AD-integrated zone configuration