Vultr.com Frequently Asked Questions - Vultr.com の通り、デフォルトではSMTPはブロックされてて、解除には写真付き証明書とか必要。
フォーラムでも言われてるけど、ちょっとハードル高い。

というわけで、メール送信クラウドサービスを使うことにした。

メール配信クラウドサービス13個の価格比較グラフを作りました（SES/SendGrid/Mailgun...） - atskimura-memo の通り、いろいろあるけど、SESの次によく名前を聞く、SendGridを選択。

無料枠は400通/日ということで、個人利用ならまず問題なさそう。

設定は、config/environments/production.rbに、

  config.action_mailer.smtp_settings = {
    user_name: ENV['SENDGRID_USERNAME'],
    password: ENV['SENDGRID_PASSWORD'],
    domain: 'example.com',
    address: 'smtp.sendgrid.net',
    port: 587,
    authentication: :plain,
    enable_starttls_auto: true
  }

を書くだけでOK。（Rails 4.1）

最初、

W, [2015-03-11T04:51:09.779586 #10210]  WARN -- : An error occurred when sending a notification using 'email' notifier. Net::SMTPFatalError: 550 Cannot receive from specified address <notifier@example.com>: Unauthenticated senders not allowed

というエラーが発生したけど、Capistranoが古くて、ENVの値が`読めてないだけだった。
Capistranoを3.2.1から3.4.0に上げたら行けた。

参考

Send Email with Ruby on Rails - SendGrid Documentation | SendGrid