ConoHa( http://www.conoha.jp/ )を契約してメールサーバーを立ててみました。
http://www.conoha.jp/blog/books/1522.html を見ればさくさく立てられる(main.cfで最後に追加するパラメーターで分けるところの空白が見えなくてそのまま書いたら続けて書いていることになってしまって起動失敗したりもしましたが)のですが、困ったことに私の使ってるプロバイダはOB25B(詳しくはぐぐってね)されてて薄い本のままではメールを受け取ることができても送れないのです。
よくある対策はGmail等を使ってメールをリレーさせる方法ですが、スマートじゃない。もっとスマートな方法は無いかと探していたらあったあった。
「/etc/postfix/master.cf」の「#submission inet n - n - - smtpd」と書いてある行のコメントアウトを外してpostfixを立ち上げ直せばば587番ポートで待機してくれます。VPSの587番ポートを開けて、メールクライアントで送信に587番ポートを使うようにしてSMTP認証もするようにするとバッチリ送れました。
ご参考までに。