ホスティングしているプロバイダや業者では「迷惑メールフィルタ」サービスはないのでしょうか？
別の方法としては、フィルタ機能の強力なメーラやツールを試用してみてはどうでしょうか。

横から失礼いたします。
当方もメールサーバを外部ホスティングしており、
モロにスパムの影響を受けております。

外部ホスティングため、ゲートウェイでのフィルタリングができず、
サーバ側でスパムを止められません。

ホスティング先からはroot権限をもらっており、ソフトウェアの
インストールは自由にできる環境にあるので、フィルタリングが
できるソフトウェア（存在していれば）を導入された経験を
お持ちの方は情報をいただきたいと思います。
OS：Redhat7.3

クライアント側の対策として、紹介されている「Thunderbird」を
検証中ですが、OUTLOOK2003からのデータ移行の際、文字コードの
変換がうまくいかないケースがあります。他おおむね良好です。
ただし、学習型のフィルタリングなので、関心の低いユーザーには
導入しづらいのでは？との話も上がっております。

もしスパムフィルター機能がないプロバイダを利用しているというのであれば、変更してはどうでしょうか。最近は移行も簡単に行えます。
規模がコンパクトな会社でしたら、自社のドメインメールが無料で使えるようです。
Gmail for your domain
Windows Live Custom Domains

または、gmailに転送しgmailのスパムフィルタ機能で分類するという方法もお勧めです。
gmailの設定＞アカウントの設定　で会社のメールアドレスを登録し、デフォルト設定を行えばそのアカウントで送信も可能です。

横から失礼致します。
当社もメールサーバをホスティングしています。
８０アカウント中、１０アカウントほど、やはりスパムが酷い状態でした。
ホスティングのオプションで、スパム除去もありましたが、オプション契約をすると全アカウント数契約となるので、費用がかさむと判断し、端末側だけの対応を行いました。
具体的には、CAのアンチスパムを導入しました。

また別途、以前からウイルスバスターコーポレートを導入していたのですが、両ソフトを入れても、特に問題は無かったです。