Exchange Server 5.5 problem

I administer a multisite network using the 192.168.x.x class B address.
Our Exchange 5.5 server is located on the 192.168.0.0 network. Users on the same network receive their internal e-mail immediately, but users at the remote sites have started receiving their e-mail between 30 minutes to one hour later.

I have checked everything including our Cisco 2620 whose IOS I upgraded and nothing has helped.
The other sites are connected by frame relay, and the netoworks are:

192.168.1.0
192.168.2.0
192.168.3.0
192.168.4.0
192.168.5.0

Thanks