The problem started after trying to migrate their Site Servers from an old Notification Server to a new one.
This migration included moving a few Site Servers from an old SMP to a new one. The Site Server was able to get the policy to upgrade the Altiris Agent and the Task Service plugin. Both the agent and the task service plugin are in the same version as the SMP. The Site Servers were being moved from SMP 8.1 RU7 to SMP 8.5.
The following error entry can be found on the agent logs from the Site Servers:
"Failed to perform re-register.
Error response returned from server: The handler 'RegisterTaskServer' is failed to process request. Registration of unsupported Task Server <Task Server GUID> version '8.5.3035.0' is rejected (expected version is '8.1.6236.0'). Please upgrade it or re-target it to another Notification Server that supports specified version of Task Server."
Removing and installing the Task Service on the affected machines seems to solve the issue.
There were more than 120 Site Servers and it was not possible to reinstall the service manually on all of them.
ITMS 8.x
In this particular scenario, there was a manual reference for the "PreferredNSHost" under the Task Service Setting on the new SMP (since they migrated the same database to the new server) that was still referencing the old SMP. That is why the error message was saying that these Task Servers were trying to register to the SMP 8.1 rather than the SMP 8.5.
SMP 8.5 and later:
ITMS 8.5 and earlier: