Mail sent on clicking the Approve button in workflow mail bounces back with smtp error

In one of our dev environments, workflow approval mails were getting bounced with this message:

Your message did not reach some or all of the intended recipients.

Subject: Action Required: Purchase Requisition 14729 for Example, User (100.00 USD) requires approval
Sent: 5/23/2008 12:33 PM

The following recipient(s) could not be reached:

mail@erp4.justanexample.com on 5/23/2008 12:37 PM
A configuration error in the e-mail system caused the message to bounce between two servers or to be forwarded between two recipients. Contact your administrator.
<>

I googled for this smtp error and found that many people have suggested having all the names of the mail server in /etc/mail/local-host-names. I have asked unix team to do this change. However I am not very sure this will work, as we do not user local-host-names in our sendmail configuration in other dev servers.

Unix team came back saying that the smtp configuration works on all other servers and they would not change it. So I checked for other instances on the same box, and found that workflow notification mailer was working fine with some other instances using the very same smtp. I checked the workflow mailer configuration screens in OAM and found that smtp unix user and password were incorrect. Workflow mailer was not running at all. After this was corrected, the approval workflow mails started going in without bouncing back.