I am having the same issue as this poster on MSDN, but the solution given did not work:
This is also a follow-up from an earlier question of mine:
NOTE: I am using WSS 3.0, not MOSS.
I have written a query to show all deleted users from the User Information List, using a CAML query where the "Deleted" field is set to 1. I see that some users with the same account have been added multiple times. When I try to delete them using all the standard methods (SPListItem Delete() method, SPWeb Remove(), RemoveByID() methods, SiteUsers.Remove() method, ProcessBatchData, etc.) I get the same error message that poster got:
Error Message: Cannot complete this action. Please try again
Error code: -2147467259
I also can't set the Deleted flag to 0. It accepts the update, but doesn't change the record. Is there ANY way to really, actually, COMPLETELY delete a user from the User Information List? I should point out that some of these users were added programmatically, and are not tied to an actual Active Directory account. However, I have tested against valid AD accounts, too; and get the same error message.