I have inherated a 2 year old problem at a new job I just started. We have a small handfull of customers who's e-mails to us are delayed by several (up to 24) hours and sometimes they get the generic exchange message domain could not be found and the transmission fails all together. These customers do not have problems sending to anyone esle, and we do not have problems receiving mail from anyone esle. All that I can think of is whatever DNS servers their message hits on the way to find us has incorrect or missing information for our domain and when their exchange server resends the message it hits different DNS servers and goes through. I have looked at the message headers on our end and see the delay is their mail server waiting to find ours.
I have used some DNS and MX tools to try and troubleshoot this issue and the servers they check come back OK for our domain.
I know I cant check every DNS server in the world to see where my info is wrong and I am not even sure if that is the problem.
I am not sure where to go from here, or if I am even on the right track, and am not getting any help as this issue has been going on for so long everyone esle has given up.