I had similar problem. We had about 10 computers sharing the same GUID - I think we deployed a manually syspreped image with Agent installed.
We also could not use psexec or similar - antivirus was picking psexec as suspicious, firewalls in place, etc... In the SMP we could see only last checked in computer as active.
In the end I used PCAnywhere command queues.
I pushed an Altiris task to the computers to reset GUID, then stop Altiris agent - both commands in the same script.
Deleted all records from the SMP by hand.
Used PCAnywhere command queue to start Altiris agent.
Computers re appeared in the SMP just fine. I bit of a manual work but it worked. This was a while back, but I can dig out my scripts for you if needed.
Another option to use is group policy and script it there if your numbers are high, but you may need to restart your clients.
Hope this helps.