Some helpful links:

http://www.sendmail.org/%7Eca/email/auth.html
http://www.jonfullmer.com/smtpauth/
http://www.joreybump.com/code/howto/smtpauth.html
http://server.1und1.com/root_server/bs/suse72/howtos/1.html
http://info.ccone.at/INFO/Mail-Archives/redhat/Jan-2002/msg02936.html
http://www.howtoforge.com/howto_sendmail_smtp_auth_tls

Please check if Sendmail/Postfix and your POP3 daemon are running by executing

netstat -tap

You will get a list of all services listening on your server.

If they are running re-configure your firewall (iptables or ipchains) so that the ports 25 (Sendmail/Postfix) and 110 (POP3) are not blocked. If this does not help please check that Sendmail/Postfix is really running on port 25 and your POP3 daemon on port 110.

(Hint for standard RedHat installations: If you have webmin installed and are running Sendmail, go to Webmin->Servers->Sendmail->Sendmail Options. Under SMTP Port Options you often find the following entry:

There are two solutions for this problem:

1) You configure your MTA to allow authentication via SMTP (SMTP-Auth). Your users then have to change settings in their email clients (e.g. Outlook), i.e., they have to activate Server requires authentication.

2) You install "POP-before-SMTP" or poprelayd on your server. Your users then have to fetch emails first before they are allowed to send emails for a restricted period of time (mostly 30 min.).