On trying to run Purge Maintenace, the logs may be showing deadlocking problems.
Notification Server 6.0 SP2, 6.0 SP3
While the cause is not completely certain, it is felt that the SQL server is probably too busy for the purging process to lock all the resources needed for the Purging Maintenance to function properly.
Pushing back the client configuration update interval may alleviate this more than anything else, but an evaluation should also be done on how much the server is actually doing, that is how many solutions, agents communicating information, custom schedules being run, and so on. All of these things could each be contributing to this problem.
An NSscript file is attached to this article that can also help. It pauses the Altiris Service (enough of it) and then calls the Purge Maintenance through the script. Pausing the Altiris Service, and the Message Dispatcher, will cause errors to show up in the the log file indicating that the process (Purge Maintenace sheduled task) was unable to communicate with the Altiris Server and failed. This script shuts down enough of the Altiris Service to allow the purging to hold onto the necessary resources.
There are probably several ways to automate this, but it is suggested that you create a scheduled task and run the NSscript using the attached file (RunPurgeMaintenance.txt). The extension needs to be changed to .cs from .txt.
%ProgramFiles%\Altiris\Notification Server\bin\nscript RunPurgeMaintenance.cs
This will run the Purge Maintenance process to completion.