My understanding is that the data isn't synchronized.  AD imports into NS, and Helpdesk pulls from NS.  NS does not store Active/Inactive data for users; that's something that Helpdesk stores for that solution only.  Therefore, because Helpdesk does not synchronize with ActiveDirectory, I think you are limited to manual updates.

Have you tried running a full User AD import on the NS?  I'm not sure it will help, since deleted User resources in AD are removed from the NS, but not from Helpdesk.

You could perform this en masse if you import data about users.  For example, if 'Department' were set to 'Terminated,' you could search for Contacts whose Department is equal to Terminated, then delete or inactivate those Contacts.

Does this help?

What I do is have a Notification Policy that runs a report for me weekly to look for excess Contacts. These would be Contacts still in the Helpdesk database but no longer in the NS database. I just remove or set 'inactive' (if they have associated tickets) the Contacts that come up on the report. The SQL I use for the report is here:

select HD.contact_name as name, HD.contact_nt_id as [NT ID]       
from [Altiris_Incidents].[dbo].[contact_view] HD        
where HD.contact_resource_guid not in (select Guid from [Altiris].[dbo].[vResource])       
AND HD.contact_status = 'a'       
order by name

I could proably automate this with Workflow but we're going to be migrating pretty soon to ServiceDesk 7.1 once it releases so I'm just going to use my trusty old report until then.