Use of DNS Alias

[DNSer]

I run a shop with W2K3 AD integrated DNS.  I also host an Exchange 2003
server.

We have a CISCO Firewall in the network and until recently I used DNS
doctoring (aliasing) to redirect requests from my inside users for the
publicly registered email server   In other words, I had a firewall
rule that specified my publicly registered email server (MX), i.e.
mail.mydomain.com, is found at mail.inside.mydomain.com.  It worked
great --there were no problems with name resolutions and email. After
maintenance on the firewall, this DNS doctoring stopped working
altogether.

This has become a real annoyance since I have a lot of branch office
and mobile users who visit
the main office and can not access email because the mail host is named
differently on the inside from the public email name.  And without
changing settings in their mail client and \ or
providing a  "new" address for their OWA, they cannot get to their
email.

I've troubleshot the problem with CISCO -- there's no way to recapture
the functionality without
changing hardware -- not a very practical solution.  I've thought there
may be a way
to do it in DNS with the use of CNAME RR.  But I've also heard there
may be problems
using cname references for mail servers.

Does anyone have experience with this type of problem and if so, how
did you resolve the
problem?  Any advice or guidance is greatly appreciated.

DNSer