Interesting question but a good one for sure.

I would suggest putting some logic to have to check and see if the name of the attachment exist as a base rule.

Secondly, use the overwrite to prevent duplicate files. Turn on versioning in the destination libraries and allow SharePoint to handle the file uploads as it should. If you upload a new document, it should create a new version without issues. Definitely, need to test but based on what I've seen with versioning. 

Versioning is turned on and using the overwrite is precisely the problem. The upload workflow action is not creating a new version the way I expect it to. I agree that it should create a new verison, but it's not.

Do you mind sharing your workflow and the name/structure of your list/libraries. I'd like to tinker with it some to see what may not be working.

In another layer to the mystery, I've discovered that this behaviour is different for another workflow where I use document sets. In the other workflow, I do basically the same steps, only now the document upload step puts the file into a document set specified by a variable. If a document with the same name already exists, the workflow uploads the document and SharePoint treats it like a new version. This is what I would expect and want to happen.

I'm wondering if this is SharePoint having different behaviour for modern and classic experiences, because when you use document sets it defaults back to classic mode, but the library where this is not working is in modern mode.

The workflow is quite long, so I'll share the relevant parts.

There's a run if action at the start so it only transfers the document if a variable is set to yes.

It then goes through the webservice call and dictionary steps to get the attachments from the list item that the workflow is running on.

Then we start the loop to transfer the documents across. It gets the specific dictionary item that corresponds to the attachment name. It then uses the upload step to put the attachment file into the document library, which is in the same site as the list. There's then a couple of steps to update metadata, which varies depending on the type of document it is, which is that short branch in the middle.

The workflow that's doing what I want is doing basically the same thing. Build dictionary, call web service, etc. Go into a loop and get the name of the attachment, upload the attachment to a library in the same site. The difference is that instead of the folder path being just "Library Name" in the working workflow it's "Library Name{variable:audit number}", where the audit number is the name of the document set.

I'm going with "this is a SharePoint being weird" thing. I tested out my theory by switching everything over to classic mode and the document versions started updating correctly. I switched back to modern and it carried on working.

So I'm no closer to understanding why it wasn't updating versions properly in the first place, but it's working now. So my answer to this problem is to switch SharePoint into classic mode temporarily to see if it gets its act together.