If I understand the scenario correctly, you could either:
1) Use IValidation.Delete() to remove existing validation to the range prior to adding new validation.
worksheet.Cells["A:A"].Validation.Delete();
worksheet.Cells["A:A"].Validation.Add(...);
2) Instead of all out deleting the old one, modify the existing IRange.Validation object to fit your new data set. You would use IValidation.Modify(...) to do this.