NDR 5.4.0 Exchange 2K

I am running Exch 2K on windows 2000. At random I will get an NDR 5.4.0 to an outside address.(DNS error) I can telnet to the domain with no problem from the mail server but for some reason mail can’t find its way. Later the mail will go through with no issues. Now it would be easy to blame this on somebody elses mail server but this can happen at any time to any address so the problem has to be at my end. I have tried switching DNS servers to no avail. Any ideas?