Exchange 2000 server delays certain mail

We have a customer that we remotely administer that runs MS Exchange server 2000 with service pack 3, on top of Small Business Server 2000. 9 months ago, an intermittent problem surfaced: Email sent to certain Domains got delayed in some of their accounts. It would take 6-15 hours for them to get the notification that the mail was delayed. The issue was fixed by manually installing the post service pack 3 rollup outdates. Just rebooting the server does not solve the problem. All delayed mail then gets sent. That fixed it for 8 months. Now it has happened 3 times this month. We install the latest rollup and it stops,,, for a while.
The installation is vanilla and updated.