Hi,
Have you downloaded and printed out the Red Hat Sendmail HOWTO. What method are you using to configure your sendmail server, linuxconf or a personalized sendmail.cf m4 compiled configuration? Also, what error messages are you receiving from the Outlook mail client when they try to connect to the server and send/receive mail?