Gateway IP & Outlook to Exchange Connect

I have my Win2000 desktops on NT LAN using the inside IP (private) address on Cisco firewall for gateway and when Outlook XP opens I get message indicating that Exchange Server 5.5 (SP4) is not responding, plus I usually get a prompt to retry or work offline. I usually only have to click retry once and then Outlook will connect. When I change my gateway to the public or outside address on my firewall, I don’t get the ‘not responding’ message or even retry prompt, in fact, Outlook starts up rather quickly. But then Internet Explorer doesn’t work–can’t find any Web sites (whereas it did before with the private IP or inside address of firewall as gateway). I don’t get it–it makes not sense to me. Anybody have an idea what’s going on?