I stand to be corrected here but the error you reported usually means there is an SMTP communications issue which you can expect if you are being blocked somewhere. The other things to look for are then routing issues such as bottlenecks. I would say its not DNS, not sure what hardware you use but may be worth looking through the syslogs and you may even find you have a problem router somewhere. If you can afford to do it go through the proces of reboots, I have an 1800 series router that often needs a restart due to a memory leak and it always effects SMTP.
