Try the below listed steps in order to remove the BE agent.
Method 1 -
1. Download Microsoft installer cleanup utility and install on exchange server. (
http://support.microsoft.com/default.aspx?scid=kb;en-us;290301)
2. Run the utility from Start --> Programs --> Windows Install Cleanup
3. Select BackupExec Agent for Windows Servers
4. Click Remove
5. Click Exit
Method 2 -
Remove Following keys from registry.
1. HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\ BackupExecAgentAccelerator
2. HKEY_LOCAL_MACHINE\SOFTWARE\Symantec\Backup Exec for Windows
3. HKEY_LOCAL_MACHINE\SOFTWARE\Symantec\DLO [If DLO is not being used].
4. Remove all RAWS files from install directories (Note: %SystemRoot% is typically C:\Windows)
Backup Exec Remote agent Installation Directory. The default installation directory is C:\Program Files\Symantec \Backup Exec\RAWS
5. Make sure that Symantec Backup Exec Remote agent for Windows Servers is not present in Add/Remove Programs.
6.Reboot the server.
7.Install RAWS manually [Please refer the tech note in related documents below.]
8. Confirm if the Backup Exec Remote agent for Windows Servers service is started or not.
9. If it still says "Starting" then try to start the Backup Exec Remote agent service from the command prompt by running the command : beremote -console
10.Open command prompt and log on to directory X:\Program Files\Symantec\BackupExec\Raws\ and type "beremote -console"
Note : {X:\ is drive letter where BEWS remote agent installed.}
11. At the end it flashes an error
12. Open an Internet Explorer,Click on Tools - Internet Options - Programs, At the Email option select Microsoft Office Outlook as the default mail client - Click Ok.
13. Restart the Backup Exec Remote agent for Windows Servers service.
Hope this resolves the problem