It started when there were emails destined to this domain (only this domain) got stuck in the queue of our Exchange Server. I tried to telnet to port 25 to the mx record for that domain from our exchange server, which is behind firewall (cisco 515), and it failed. I can't telnet from anywhere behind firewall either. But I can telnet directly behind the router, bypassing the firewall. This problem is, this is intermitten. When I can start to telnet again (behind firewall), the mails in the queue will go thru.
I have disabled the smtp and dns fixup protocols at the firewall.
I also asked my friend to telnet from other countries, they've got no problem.
I'm pretty sure it lies within our firewall. I just don't know what else to check cause it only affects this one particular domain.
If anyone can tell me where else I have to check, it would be much appreciated.