Were these computers imaged from the same image?
     If yes, was the Altiris Agent installed on the computer that the image was made from.

The reason I ask these questions is that it kind of sounds like a duplicate GUID issue.  I would delete the offending computers out of the NS resources and run the following vbscript on the workstations: 

<Start of Script>
'vbscript Change GUID then force client to update configuratin and send basic inventory
Dim WshShell
Set WshShell = WScript.CreateObject("WScript.Shell" )
Dim TypeLib, sNewGuid
Set TypeLib = CreateObject("Scriptlet.TypeLib" )
sNewGUID = TypeLib.Guid
Set TypeLib = Nothing
sNewGuid = left(sNewGUID, len(sNewGUID)-2)
' wscript.echo " # Guid Generated " + sNewGuid
WshShell.RegWrite "HKLM\Software\Altiris\Altiris Agent\MachineGuid" ,sNewGuid, "REG_SZ"
WshShell.RegWrite "HKLM\SOFTWARE\Altiris\Client Service\NSMachineGuid" ,sNewGuid, "REG_SZ"
WshShell.RegWrite "HKLM\SOFTWARE\Altiris\eXpress\MachineGuid" ,sNewGuid, "REG_SZ"
WshShell.RegWrite "HKLM\SOFTWARE\Altiris\eXpress\NS Client\MachineGuid" ,sNewGuid, "REG_SZ"
WshShell.RegWrite "HKLM\SOFTWARE\Computing Edge\Notification Server\MachineGuid" ,sNewGuid, "REG_SZ"

Dim client
Set client=WScript.CreateObject ("Altiris.AeXNSClient" )
ignoreBlockouts=1
sendIfUnchanged = 1
client.SendBasicInventory sendIfUnchanged, ignoreBlockouts
client.UpdatePolicies ignoreBlockouts
<End of Script>

This script will make the workstation reset its GUID and report back in.  This should clear up the issue.

Hope this helps