I am batching the data loader to do upserts to five objects, using external IDs that need to be unique so that I can make sure to reference the same salesforce records every time I run the upsert, since each time, some of the records will have some different values.

The problem I'm having is that sometimes the records are updated when a match is found that already exists, and sometimes it gives me the error "duplicate value found". It's about a 50/50 split between the outcome that I want and the error messages. In theory, I shouldn't ever get any error messages when I re-run the upsert, since it should just update the records to the new values.

Removing the unique restriction on the external ID is not an option for me, as it just defeats the purpose of me using one completely if more than one record can have it.