If they're set up internally, I assume you have an internal DNS setup that's all nice and set up.
Try split DNS to handle the NATTING. Here's an example:
Internal server (mail.domain.com) <-> Internal DNS (dns.domain.com)
Internal deliveries are handled with the help of internal DNS.
Outside DNS A <-> Public IP <-> Router:Nat rule for webmail port (80) <->Mail.domain.com <-> Internal DNS <-> Internal Clients
I don't know if that makes any sense, but you want your DNS to reflect yoru ourside DNS that way you don't have that problem. Take a look at the wiki split dns entry
