The preferred method would be to use the aexagentutil.exe in the program files/altiris/altiris agent folder with the /clean switch. That process calls the AeXNSClientUninstall.exe.
Another method is to run the AeXNSClientUninstall.exe on its own. In testing, this removed the agent, all subagents, the Altiris Agent folder, and the registry keys for the agent and the services. The file is located in the \program files\altiris\notification server\nscap\win32\x86\NS client package folder.