Two things I would try first. One, go to the SMTP properties and click on the Delivery tab. Click on Advanced and then click the configure button. Type in two or three external DNS servers. Second, make sure you have a reverse DNS record set up by your ISP. I mostly had trouble sending emails to the AOLs, Earthlinks, etc of the world. I found an article stating that the DNS resolution should be done by external DNS. I can’t remember why at this point but once I made the chance I did not have any further problems. Reverse DNS goes without saying as to why you should have it setup.
A lot of connection issues have to do with larger ISPs setting up security settings in attempts to thwart spam.