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

[Alsodan]

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

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

Oct 23 10:40:21 paulaner-krd sendmail[15386]: t9N8eLfP015386: from=www-data, size=129, class=0, nrcpts=1, msgid=<201510230840.t9N8eLfP015386@paulaner-krd.ru>, relay=www-data@localhost
Oct 23 10:40:21 paulaner-krd sm-mta[15387]: t9N8eLHl015387: from=<www-data@paulaner-krd.ru>, size=356, class=0, nrcpts=1, msgid=<201510230840.t9N8eLfP015386@paulaner-krd.ru>, proto=ESMTP, daemon=MTA-v4, relay=localhost [127.0.0.1]
Oct 23 10:40:21 paulaner-krd sendmail[15386]: t9N8eLfP015386: 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 (t9N8eLHl015387 Message accepted for delivery)
Oct 23 10:40:21 paulaner-krd sm-mta[15388]: t9N8eLHl015387: to=<table@paulaner-krd.ru>, ctladdr=<www-data@paulaner-krd.ru> (33/33), delay=00:00:00, xdelay=00:00:00, mailer=local, pri=30585, dsn=2.0.0, stat=Sent

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