What version of Exchange Server; 2000, 2003, 2007?
Do you have a connector created to send to the * (wildcard) domain?
Is the server attempting to connect to the destination server(s) directly or sending through a smart host?
Is this happening to ALL outbound email or certain domains?
From the exchange server, can you resolve (via NSLOOKUP command) the domain names that you're trying to email to?
What kind of internet connection at the site where the exchange server is located?
Is it a dynamic IP? If dynamic, you should upgrade to a static account?
I've given you more questions than answers I know, but respond with the info and we can help you.