Well, I made some progress. I managed to reboot the host early this morning (that's a chore and a half with all its virtual machines) and after tinkering for a while, managed to uninstall the agent with:
c:\temp\rawsx64\Install\Media>msiexec /uninstall "Symantec Backup Exec Remote Agent for Windows Systems.msi"
Then I was able to remote push-install the agent from my Backup Exec server. The reboot must have been the key to the solution. It just sucks to reboot my host due to the guests it has on it.
However, the next problem was that the service "Backup Exec Error Recording Service" had been set to Disabled and hadn't gone away when the uninstall happened. So when the re-install did its thing it could not create this service again. When I tried setting it to Automatic Start from Disabled, Windows threw a message "The service is marked for deletion". With more Google research, it turns out the uninstall wanted another reboot in order for Windows to fully remove the service. I probably should have waited until rebooting a second time before re-installing.
