If you come across the following error it is because Exchange cant query the domain. If you ping the domain name it will give you an error saying it cannot find it.
Simple fix, under organization management -> Hub Transport -> Send Connector, right click on your send connector and select properties. On the network tab check the box that says Use External DNS lookup settings on the transport server.
Then under Server Configuration -> Hub Transport right click on the server name and select properties. Click the External DNS lookup tab and then “Use these DNS servers” and enter in your ISP DNS entries.
Click Okay and then refresh your queue and mail should start going out.
Hope it helps.