1. Have you tried telneting to the remote mail server? telnet {server name or ip address} 25
The banner should have some information.
4. When you say you "can telnet to port 110 and 25 once connect outside the proxy server", what do you mean? In other words, can you telnet to the two ports from a workstation inside your LAN, or from outside your LAN? What is the gateway address of that workstation - the proxy server or the router?
5. When I mentioned dovecot.conf I meant the IMAP/POP service in the remote email server. That entry is obviously irrelevant if you say that the remote service supports POP3.
When you say "the mail server is accessible if not connected to the proxy server", what do you mean precisely? Your POP3 and SMTP do not have to go through the proxy server, unless it runs some sort of mail proxy, too. In that case you should look at the configuration of the mail proxy. As far as I know, having installed squid and support it in production, squid caches only HTTP traffic. I assume your workstations are PCs running Windows: you point the workstations to the proxy in Control Panel Internet Options - Connection, but the POP3 and SMTP traffic are directed in the TCP/IP settings according to the entry in 'Gateway' to either your proxy server, if your Fedora 4 server acts as the firewall of all the incoming packets from outside, or to your router which, depending on the model, may also have firewall capabilities.
If you turned iptables off, you can be in trouble very soon if the network is exposed.
By the way, do the email clients specify the IP address or the domain name of the remote mail server? Your problem may caused by a problem in DNS lookup as well.