Exact same problem here, except my server is a W2K member server running E2K. Backup of files works fine, backup of Exchange works fine (with error messages however), but anything that depends on the agent fails, like System State. I too have tried just about everything to get this to work, including the fix mentioned earlier (registry change AddedToRNR) My service account has Domain admin and Exchange Full admin rights, so its not a rights issue. You can see the server in the Backup Exec selections window, and when you look at the properties it says the agent is installed and running (version 8.60.3878.0) This failure has nothing to do with Exchange, it has to do with Backup Exec. This error occurs with any type of backup of the remote server - System State, Exchange or File.
I'm starting to get a little PO'd with this problem, and the lack of information on the Veritas site to deal with it. It is very likely a problem with the product, or they are leaving out some critical information on how to set this up. I have followed the instructions to a 'T' and I'm sure the other folks on this thread have also done so.
Does anyone have a service contract with these people? Perhaps get a call going?
D