Relaying denied

In one of our environments, the mail server was changed. Previously the SMTP server was configured as the Exchange Server. It was changed to Sendmail. However sending mail to any external domain was giving this error:

Relaying denied

A google search revealed a page about Controlling SMTP Relaying. However, none of the steps applied to us. Mail was working fine from other servers created with the very same OS image.

A simple smtp commandline test is to

First connect to the Apache/Forms tier with telnet

telnet apache.justanexample.com

Once you are logged in

telnet sendmail.justanexample.com 25

MAIL FROM:vikramdas@justanexample.com
RCPT TO:mailuser@justanexample.com

Relaying Denied.

However if I connected to a different server instead of connecting to apache.justanexample.com:

telnet qaserver.justanexample.com

telnet sendmail.justanexample.com 25

MAIL FROM:vikramdas@justanexample.com
RCPT TO:mailuser@justanexample.com

Recipient OK.

I am still investigating what is causing Relaying Denied error. As a workaround, we changed the configuration and pointed SMTP server field in workflow mailer configuration to a different sendmail server. We verified in the same way as described above. This worked. However I am still trying to find out what was causing the Relaying denied message from the previous server. I'll update this post once I find out.