This problem has several symptoms.
The immediate cause of the problem is that a Software Delivery Task and Package has been deleted on the Notification Server before it is removed on the clients. The following sequence of events highlights the problem.
Remove the task entry from the aexswdpolicy file.
One possible way to automate this is to run the following command script via a Software Delivery job. This script will stop the Altiris Agent, rename the aexswdpolicy.xml file, delete the client config policy file (this step is unnecessary, but useful), and restart the Altiris Agent. Because the information about the execution of this Software Delivery task is stored in the aexswdpolicy.xml file and since the file is renamed, the agent will run this job twice. The first time, it will create a new aexswdpolicy.xml file that does not have the task execution information in it. The agent will think it has not run the job and will execute it again. The second time it will not be able to perform the rename, since the .bak file already exists and so the task execution information will be retained.
rename ..\..\aexswdpolicy.xml aexswdpolicy.xml.bak
del "..\..\..\Client Policies\*.xml"
Important: Since all task execution information will be lost, the agent will run every task as configured in the client config policy file, whether it has previously run the task or not.
Notification Server 6.0 SP3 (6.0.6074)
Software Delivery Solution 6.1 SP2 (6.1.1049)
Previous versions will most likely exhibit the same problem.