AMUAMUさんは書きました：
EC-CUBEではありませんが当方ではさくらの共用、専用共にPHPとPerlから正常に送れています。

さくらのレンタル専用サーバの場合
・最新のRFCルールに則ってDNSやMAILサーバを徹底した設定で運用していない場合。例えば逆引き名など。
・過去に当該送信元IPまたはドメインで悪例が無いこと（ブラックリストに入っていないこと）。
・古いバージョンのSMTPサーバを動かしている場合。
これらの時に、自動的に拒否される場合があるようです。

さくらの共用レンタルサーバの場合
・適切なDNSの設定がされていない。
・適切なメールヘッダを入っていない。
・共用サーバ内で一定数以上のメールがYahoo!ドメインに送信した、した実績がある（ドメインではなくサーバ単位）。
・共用サーバ上で同居している他人の過去のスパムメール送信実績により共用サーバのIP単位で拒否されている場合。

後半の2例の場合はYahoo!確認後に、さくらに文句を言うと移転させてくれた事例が過去にはあったそうですが、基本的には諦めるしかないと思います。共用サーバのリスクや問題ですので、ある程度は我慢しかないと思います。

なおメール送信の為のSMTPサーバをローカルではなく外部メールサーバ経由にすることで回避出来る場合もあります。

ご参考までに。