Ed,
I run SME 5.6 at work as our mail server in server-only mode. It has one NIC in it, is routed through a SnapGear firewall/VPN router (gateway) and works fine. Our users have their SMTP and POP3 server set to the internal IP of the SME server for sending and receiving mail. We do not have webmail enabled, and only one travelling user accesses the SME server through it's external IP address (via the SnapGear.)
We don't have nearly as complicated a network as you do, however, We essentially run from our ADSL modem, into the SnapGear, into the ethernet switch, and from there to all machines in the network, including the mail server. We've never had a problem sending or receiving mail in this manner.
It's possible a similar setup wouldn't work for you, as your complicated firewall rules might prevent things from crossing subnets. Do all users on all subnets have this problem? What about users on the same subnet as the SME server?