おひさしぶりです。ご質問ありがとうございます。
CGI からの送信は迷惑メールと判定されやすい傾向があります。記載されたリンクが多いことなども影響するようです。
ご指摘のように、さくらのレンタルサーバではメールサーバがお使いの独自ドメインと別のドメインとなりますので、そのことが悪影響している可能性はあるかと思います。
とりいそぎ、サイトの目立つところで、迷惑メールに入っていないか確認するよう促すしかないように思います。
迷惑メールに入ることを回避する方法があれば、迷惑メールシステムそのものが意味のないものとなりますので、なかなか解決は難しいのではないでしょうか。
あまりお役に立てず残念ですが、以上参考になりましたら幸いですm(_ _)m。