Do you have the latest service packs and hotfixes installed on your Exchange 2000 servers? You should have the Exchange 2000 Server post-service pack 3 rollup fix installed, as a minimum. This fix is described in Microsoft Knowledge Base Article 813840 "XGEN: March 2003 Exchange 2000 Server Post-Service Pack 3 Rollup" and the fix can be downloaded here. Make sure you are running the March 24, 2003 version of this hotfix and not the earlier version (the hotfix was re-released).
Applying this rollup hotfix should resolve your problem. If it doesn't, let us know and we'll follow-up some more.
This was first published in October 2004