Sendmail и почта на внешнем сервере (Яндекс)

[Alsodan]

Добрый день! Я недавно начал знакомство с Ubuntu, раньше пользовались Shared-хостингом, а сейчас переехали на VDS.
У меня такая проблема:
Есть сервер, на нем развернут LAMP. Крутится сайт.
Почту для сайта решили развернуть на Яндексе. Сделали по инструкции https://yandex.ru/support/pdd/add-domain/add-exist.xml
В качестве MTA стоит Sendmail. При попытке отправить письмо из формы обратной связи - показывает, что все в порядке.
В логе видно, что есть проблемы.
Лог:

(Нажмите, чтобы показать/скрыть)

sendmail[4980]: t9NANwTL004980: from=www-data, size=129, class=0, nrcpts=1, msgid=<201510231023.t9NANwTL004980@hosting2.it.europeya.ru>, relay=www-data@localhost
sm-mta[4981]: t9NANwWx004981: from=<www-data@hosting2.it.europeya.ru>, size=372, class=0, nrcpts=1, msgid=<201510231023.t9NANwTL004980@hosting2.it.europeya.ru>, proto=ESMTP, daemon=MTA-v4, relay=hosting2.it.europeya.ru [127.0.0.1]
sendmail[4980]: t9NANwTL004980: to=table@paulaner-krd.ru, ctladdr=www-data (33/33), delay=00:00:00, xdelay=00:00:00, mailer=relay, pri=30129, relay=[127.0.0.1] [127.0.0.1], dsn=2.0.0, stat=Sent (t9NANwWx004981 Message accepted for delivery)
sm-mta[4983]: t9NANwWx004981: to=<table@paulaner-krd.ru>, ctladdr=<www-data@hosting2.it.europeya.ru> (33/33), delay=00:00:00, xdelay=00:00:00, mailer=esmtp, pri=120372, relay=mail.paulaner-krd.ru. [5.200.55.45], dsn=4.0.0, stat=Deferred: Connection refused by mail.paulaner-krd.ru.

И письма на Яндексе не видно.
В чем может быть проблема? 

[AnrDaemon]

В неверной настройке sendmail. Оно пытается отправлять письма напрямую.
Вам нужно настроить отправку всего почтового трафика через яндекс, кроме локального конечно.

[Alsodan]

На все почтовые ящики, кроме того домена, для которого почту настроили на Яндекс, письма отправляются. Может дело в DNS-записях? Сейчас они такие:

(Нажмите, чтобы показать/скрыть)

$ORIGIN paulaner-krd.ru.
$TTL 3600
paulaner-krd.ru. 3600 IN SOA ns01.1cloud.ru support.1cloud.ru. 1 1800 900 604800 120
paulaner-krd.ru. 86400 IN NS ns01.1cloud.ru
paulaner-krd.ru. 86400 IN NS ns02.1cloud.ru
paulaner-krd.ru 3600 IN A 5.200.55.45
paulaner-krd.ru 3600 MX 10 mx.yandex.net.

[AnrDaemon]

Это интересное уточнение… тут я не помогу, сам с сендмейлом не работаю.
Попробуйте ещё раз проверить настройки локальной почты, какие домены прописаны и т.п.
Можете попробовать написать в поддержку яндекса, только постарайтесь максимально конкретно описать проблему.