sendmail DSN: Service Unavailable

We have for one of our clients a mail relay server based upon sendmail, running on a ubuntu machine.

From the logs (tail -50 /var/log/mail.log) we get:
Apr  7 17:19:04 HBDS1043 sm-mta[2577]: m37FJ3Zc002577: to=from.user.accounttodomain.com, delay=00:00:01, xdelay=00:00:01, mailer=esmtp, pri=30000, relay=mail.todomain.com. [xx.xx.xx.xx], dsn=2.0.0, stat=Sent ( <200804071519.m37FJ3Zc002577@sendmail.domain.local> Queued mail for delivery)
Apr  7 17:41:27 HBDS1043 sm-mta[3969]: starting daemon (8.13.5.20060308): SMTP+queueing@00:10:00
Apr  7 17:42:19 HBDS1043 sm-mta[4150]: starting daemon (8.13.5.20060308): SMTP+queueing@00:10:00
Apr  7 17:43:26 HBDS1043 sm-mta[4166]: m37FgrES004166: from=from.user.accounttodomain.com, size=10, class=0, nrcpts=1, msgid=<200804071543.m37FgrES004166@sendmail.domain.local>, proto=ESMTP, daemon=MTA-v4, relay=sendmail.domain.local [192.168.161.139]
Apr  7 17:43:32 HBDS1043 sm-mta[4168]: m37FgrES004166: to=to.user.account@todomain.com, delay=00:00:13, xdelay=00:00:06, mailer=esmtp, pri=120010, relay=mail.todomain.com. [xx.xx.xx.xx], dsn=5.0.0, stat=Service unavailable
Apr  7 17:43:32 HBDS1043 sm-mta[4168]: m37FgrES004166: m37FhWES004168: DSN: Service unavailable
Apr  7 17:43:32 HBDS1043 sm-mta[4168]: m37FhWES004168: to=from.user.accounttodomain.com, delay=00:00:00, xdelay=00:00:00, mailer=esmtp, pri=30000, relay=mail.todomain.com. [xx.xx.xx.xx], dsn=2.0.0, stat=Sent ( <200804071543.m37FhWES004168@sendmail.domain.local> Queued mail for delivery)

With a highlite to:
dsn=5.0.0, stat=Service unavailable

Also if i try to do "telnet localhost 25" we get:
Trying 127.0.0.1...
telnet: Unable to connect to remote host: Connection refused


A quick search on google http://www.adamsdesk.com/be/archives/2005/09/09/sendmail-dsn-service-unavailable/ gives me the error is probably located in the hosts or hosts.allow file in the etc folder. But it seems to me those are setup correctly.

Can this be related to another issue?
Start Free Trial