Email outside of local domain not working

I'm running Domino server, with some users using pop3/smtp. The problem is when using pop3 and smtp, the users can only send mail to co-workers within the same domain. When sending a mail to someone outside the network, it fails. It works perfectly when you are outside the network.

So some users are using Domino as a regular mail server -- fetching their mail with POP3 and sending mail with SMTP. But they are unable to send mail outside of their own email domain.

This definitely works. I have done it many times on different systems. There must be something wrong with the way mail routing is set up, or the SMTP settings in the Server/Configuration document, or the mail settings in the Server/Server document, or something else. There are a number of settings you must get correct for all aspects of email delivery to work right.