はじめまして。

わたしも同じような現象に悩みました。
解決したやり方は以下の通りです。

1.smtpサーバを指定する。
管理画面の[システム設定]->[パラメータ設定]から
「SMTP_HOST」を"127.0.0.1"から使用するsmtpサーバに変更する。

2.SMTP認証の設定を追加する。
/data/class/SC_SendMail.php
の
getBackendParamsの
case defaultの連想配列に以下を追加する。
---
,'auth' => true
,'username' => 'xxxx' // 適切なものを指定
,'password' => 'xxxx' // 適切なものを指定
---
"auth"はSMTP認証を使用するかどうかを指定します。
TRUEでSMTP認証を使用し、FALSEでSMTP認証を使用しません。
ユーザ名やパスワードはSMTP認証に使用するユーザ名とパスワードを挿入します。

この方法でメールが送信されるようになりました。

わたしは今回初めてec-cubeを使ったサイト構築をしております。
正しいかどうかは自信はありません。
あくまでご参考までに。。。