Hi there,
I've had this on a couple of occasions.
Symantec is going to suggest you install the latest service pack for your Backup Exec version. I'd suggest doing the same, and then pushing your RAWS agents out to the servers in question.
However, my fix was to remove the Exchange license key, restart the services, and then re-add them back before restarting the services again. I use BE 12.5. It seems as if the license key got corrupted somehow, but I could never pin-point.
The only other explanation was that this happened due to my temporary licenses expiring before I received my Exchange license key.