Intermittent Mail exchange problem

A customer of ours has a mail server hosted with some other service provider. He has a linux based proxy-cum-mail server configured on our link. It is observed that sometimes he is not able to either pull or push mails from his mail server, though he is able to browse the internet seamlessly. When he connects the same server on dial-up he is able to pull-push his mails. Could anybody help me out with this?!?

The nslookup resolution is taking place and I am able to resolve his domain continuously from his machine.