To trouble shoot an issue such as this, often you need to take a structured approach.
First, do your clients have a default gateway defined? Test to see if the default gateway is reachable.
Next, verify that the router on the client network has a route to the mail server network, or a default that will deliver the packet to a router that does know about the network that the mail server resides.
Third, Does the mail server have a default Gateway, and does that router have a route back?
Fourth, are there any firewalls, or route filtering that might hinder mail transfer.
Fifth, document which routing protocol(s) that are running.
Sixth, verify that the hops are on subnets of one network. If not, verify that the protocol in use is classless.
Seventh, Post a few more details. ;)
Regards;
Doug