Have you looked to see if everyone has personal contacts in the file,

My users keep personal contacts local and company contacts on the server.

Also we have one person who does all the admin on the database i.e. everyone has write privilages to a "Contact so be inserted" category and that is it, every couple of days the admin goes in and puts the contacts in the right categories.

This keeps massive deletions to a minimum.