I've been fighting a simular problem now for over a month without any good resolutions. I've just spent the morning searching, and all I find is "Veritas Support has no answers" which I find very disturbing. There are ton's of postings in the news groups about the remote agent failing on exchange server, most seem to have happened after installing SP1 for 9.1.
I did however find a posting to where the tech installed the advanced remote agent ver 9.0 on his exchange box and left the media server at 9.1 sp1, which resolved his issue. Kind of makes sence, though you would think you could also go back to pre sp1 for the remote agent on Exchange.
I'm totally open to what anyone has to offer.
Presently, I show the following for agent versions on this particular system:
media server: 9.1.4691.35
exchange server: 9.1.4691.14
other servers: 9.1.4691.0