LAN Users, ISP mail accounts, and NAT

We are behind a firewall which performs NAT. Some of our Users are trying to access email accounts hosted by other ISP’s (using Outlook, not a Browser) and are unable to receive their mail. The suggestion was to add every possible IP# that they could go out to the Internet on into our DNS table as “A” records. Is this for real? Any other solutions? Thanks.