Requesting Data messages across a WAN

I have WAN users getting ?operation failed? on IM thru Exchange, Outlook hanging and Requesting Data messages.

I have two frame relay circuits using different routers. HQ has all of the domain controllers and one Exchange 2000 server.

If I do a continuous ping from HQ to either a DC or the Exchange server I get all replies.

If I do a continuous ping from a remote location to a domain controller I get all replies.

If I do a continuous ping from a remote location to the Exchange server I get about 4 minutes of replies with about 2 minutes of Request Timed Out then back to replies and then time outs again. This pattern happens from all remote locations. I've pinged from remote PCs and the remote routers and I get the same pattern. During the time outs Outlook hangs.

Any ideas on what might cause this?