POP before SMTPが原因。
ほとんどのプロバイダの場合、最初にメールの受信確認をしてからでないと送信できない設定になっています。これは、スパム（迷惑）メールを防止するためです。メールの送受信の際に正規ユーザーかどうかを確認する方法はメール受信にようPOP認証しかなく、メールの送信（SMTP）は認証機能をもっていません。
ですので、メールの送信ができない場合はまず”受信をしてから送信”をしてください。