This is due to a problem with the exchange agent..
You must make sure that the following is in place:
1- make sure your ARCserve 2000 server is build 1086 (or sp3)
2- make sure that you have applied sp3 to the exchange agent as well and should be build 414.
3- then apply qo06202.caz to the exchange agent.
This should bring you to the latest builds and should provide you with the latest fixes, I know your error well, and these patches do solve it, however if they don't then the problem must be with the configuration of the agent, not the actual agent itself.
Oh and the exchange agent build can be seen by going into the registry and HKLM/software/computer associates/arcserve/dsagent,..../..../.../ etc.. It's there at the end of that tree.
good luck with this and I hope this has helped you out.
guru