ideally, when a system like this starts, you'd prevent the Altiris service from running so it can't check in. Then, that system could have the AexAgentUtil run on it to reset the GUID, and THEN start the service, or clear the registry key with the GUID or something so that it doesn't report in with the same GUID at any time.
How to do that? Hmmm... Not sure.
Otherwise, mop-up may be your only option. it might be ugly for a short time, but with some diligence, you should be able to clean things up.
I think, were it me mopping things up, I'd send out a GPO disabling the agent, then ensure that all the systems were uniquely named, clean up the DB from all the bad records, wipe the GUID from the registry on those systems via GPO again, and re-enable the agent. Or, alternatively instead of wiping the GUID, pull the agent, and then re-push it. Either one might work.
My fear is that anything less thorough might leave you never knowing if everything is cleaned up or not. :P