http://www.altirigos.com/vbulletin/notification-server/61-how-manual-remove-altiris-agent.html

Run through the following steps to fully remove the Altiris Agent.

1. Run the following command line to remove the Altiris Agent using AeXAgentUtil.exe located by default at C:\Program Files\Altiris\Altiris Agent\:
* AeXAgentUtil.exe /uninstallagents /clean
* This will remove all sub-agents and attempt to cleanly remove the Altiris Agent from the system.

2. Delete the following Program files if still present:
* C:\Program Files\Altiris\Altiris Agent

3. Delete the following registry keys if still present:
* HKEY_LOCAL_MACHINE | SOFTWARE | Altiris | Altiris Agent
* HKEY_LOCAL_MACHINE | SOFTWARE | Altiris | eXpress ***DO NOT DELETE THIS Key if you are removing the agent from the Notification Server itself.
* HKEY_LOCAL_MACHINE | SOFTWARE | Altiris | Scheduler
* HKEY_LOCAL_MACHINE | SOFTWARE | Altiris | APackageStub
* HKEY_LOCAL_MACHINE | SOFTWARE | Classes | All sub items beginning with Altiris.
* HKEY_LOCAL_MACHINE | SOFTWARE | Classes | AppID | {5E038245-CF81-44BE-8018-9A2981B9DC9B}

4. Search in the Windows directory <WINDIR> using the string below and delete the found files.
* AeX* 

Maybe this will work:

REM Force Altiris Update

start /wait sc stop CarbonCopy32
start /wait sc stop AeXNSClient

ping localhost -n 25

reg delete "HKLM\SOFTWARE\Altiris\Altiris Agent" /v MachineGuid /f reg delete "HKLM\SOFTWARE\Altiris\Express" /v MachineGuid /f reg delete 
"HKLM\SOFTWARE\Altiris\Express\NS Client" /v MachineGuid /f reg delete
"HKLM\SYSTEM\CurrentControlSet\Services\AeXNSClient

rmdir "C:\Program Files\Altiris\Altiris Agent\Client Policies" /S /Q rmdir "C:\Program Files\Altiris\Altiris Agent\Software Delivery" /S /Q rmdir "C:\Program Files\Altiris\Altiris Agent\Tasks" /S /Q rmdir "C:\Program Files\Altiris\Altiris Agent\Queue" /S /Q rmdir "C:\Program Files\Altiris\Altiris Agent\Logs" /S /Q

REM Following for messed up installations
rmdir "C:\Program Files\Altiris\Client Policies" /S /Q
rmdir "C:\Program Files\Altiris\Software Delivery" /S /Q
rmdir "C:\Program Files\Altiris\Tasks" /S /Q
rmdir "C:\Program Files\Altiris\Queue" /S /Q
rmdir "C:\Program Files\Altiris\Logs" /S /Q

REM Following For Older Clients

rmdir "C:\Program Files\Altiris\Express\NS Client\Client Policies" /S /Q rmdir "C:\Program Files\Altiris\Express\NS Client\Software Delivery" /S /Q rmdir "C:\Program Files\Altiris\Express\NS Client\Tasks" /S /Q rmdir "C:\Program Files\Altiris\Express\NS Client\Queue" /S /Q rmdir "C:\Program Files\Altiris\Express\NS Client\Logs" /S /Q

start /wait sc start AeXNSClient
start /wait sc start CarbonCopy32