サイト名を変更し、サイト名の文字数を増減させた所、正常にメールが送信されるようになりました。
情報古いですが、以下と同じような事象と思われます。

http://svn.ec-cube.net/open_trac/ticket/326

暫定的には以下のいずれかで対応が出来そうです。
　・ショップ名の変更
　・MailService.php のsetFromでショップ名を加えないようにする

根本対応方法までは力及ばずでした。
長くやり取りをして頂いていており大変恐縮なところですが、もしご知見がありましたらご教授頂けると幸いです...。