Well, there are probably several ways to fix this, but here are a couple ideas.
When deploying the Agent, make sure you check the box for "Install over an existing version" (that's not the exact wording; I'm doing this off the top of my head). That should remove any existing installation, whether it's attached to the current ePO server or not.
When uninstalling from an individual system, try "frminst.exe /forceuninstall" to remove the Agent.
Thanks tkinkead, but I already tried and it didn't work.
The only way I managed to do it was doing it manually but that's not a solution.
I need to do something automatically.
When you say "manually", what do you mean? Frminst.exe /forceuninstall?
Do you have SCCM or BigFix or another platform you could use to run a script across your environment? Heck, you could probably use the EEDK to write a script that uninstalls the Agent and push it out to all the necessary systems.
Make sure that the Credential for agent installation has the proper rights for the install. Pull the log from the temp folder; may provide some additional insight as to why it's failing.