I have a very similar issue. I have BU Exec 10d service pack3 with Exchange, remote servers, and DLO options installed on a Win2k3 server backing up one Exchange 2003 server on a w2k3 server. For days it runs flawlessly, then one or two days in a row it gets "Access not permitted with this version" when backing up Excahgne (data is fine) then the next day it backs up fine again. I called before and was told maybe the Key was corrupted so I deleted the Exchange agent key, rebooted, then reloaded the key and rebooted again. As expected it ran a while OK then got the error, then ran then got the error. It has gotten it again.
I can't go to 11 as it will require me to load Remote and DLO agents on all my systems and I can't undertake that just yet, and there is no way to know of that will actually fix it.
The support case indicates a change from Emal mode to licensed mode, I am running licensed, and as I said, it works for days, then fails, then works again.