It's based on GUID. Altiris always understands things by their GUIDs. Rarely (never?) will something be identified by name.
You need to include a retirement/deletion step in your reimage process so that your IT Support Techs understand that an asset must be removed from Altiris prior to the reimage. The replaced hard drive must be triggering enough of a hardware change that the NS wants to assign a new GUID. It's the same thing if a motherboard were being replaced -- it appears as a hardware change so the GUID is reassigned, since the NS doesn't know it's seeing the same system.
I wouldn't tighten your purge policies -- I think adding a manual removal step to your reimage process makes sense. Alternatively, create an exception report that runs using a notification or automation policy (not sure which version you're running) and provides a list of all computers with duplicate names, including last check-in time and GUID. You can verify duplicates manually and delete them, or, if you have confidence, could use the results of a report in an automation policy that deletes the record from the NS. (To do something like this, you would want to pull all computers that are duplicates that have not reported for more than 7 days.)
Does this help?