I run the following in a batch file to ensure clean removal of the old agent(s):
C:
"C:\Program Files\Altiris\Altiris Agent\aexagentutil.exe" /DeleteDevices
"C:\Program Files\Altiris\Altiris Agent\aexagentuti.exe" /UninstallAgents
"C:\Program Files\Altiris\Altiris Agent\aexagentutil.exe" /Clean
"C:\Program Files (x86)\Altiris\Altiris Agent\aexagentutil.exe" /DeleteDevices
"C:\Program Files (x86)\Altiris\Altiris Agent\aexagentutil.exe" /UninstallAgents
"C:\Program Files (x86)\Altiris\Altiris Agent\aexagentutil.exe" /Clean
I use both the 32bit and 64bit paths. Even if it errors, the batch file will continue and locate the appropriate path to aexagentutil.exe
My batch file also deletes (not shown) the Altiris folder via 'RD' commands before installing the new agent. This is optional, but for our environment, this ensured that no remenants of old inventories, or other conflicting files were present. (Just make sure you don't delete the Altiris folder on any Altiris infrastructure servers!)
I still ran into some stubborn ones that didn't uninstall properly, but for the vast majority of my clients (3000+) this was effective.