Entity Framework: Insists on adding new entity in many-to-many instead of re-using existing FK

You didn't specify what context model are you working with, so I'll assume you're using the default (ie. you don't have some explicit .tt files to generate your entities).

So, basically, this is what I think is happening.
In your code, when you fetch something from context:

Dim ct = ctx.CaseTypes.SingleOrDefault(Function(x) x.Identifier.ToUpper = c.CaseType.Identifier.ToUpper)

this ct is in context. The method argument that you deserialized from service (the c) is not in context. You can regard the context as the "object tracking and fetching" entity, that makes sure that everything attached to it can know about any changes, if it's new, deleted etc.

So, when you get to the part:

 ' Set the case type based on that found in database: '  c.CaseType = ct

at the moment you assign something that's attached to something not attached, the unattached object will get pulled into context as well - there can't be "partially" attached entities - if it's attached, everything it references has to be attached as well. So, this is the moment where the c gets "dragged" into the context (implicitly). When it enters the context, it will get marked as "new" since it doesn't know anything about it yet (it has no knowledge of it, no change tracking info...).

So, now that everything about that object c is in context, when you query the context for this:

 Dim s As CaseSubject = ctx.CaseSubjects.SingleOrDefault(Function(x) x.CRMSPIN = spin)

it will figure that indeed there is an object with that CRMSPIN and it's already attached - "hey, no need to go to database, I already have this!" (trying to be smart and avoid a db hit), and it will return your own object.

Finally, when you save everything, it will be saved, but your attached c and all of it's child objects that are marked as 'new' will be inserted instead of updated.

The easiest fix would be to first query everything you need from context, and only then start assigning it to properties of your object. Also, take a look at UpdateCurrentValues, it may also be helpful...

OK: So the resolution to this was a combination of what @veljkoz said in his answer (which was very useful to help me out to reach the final resolution, but on its own was not the full resolution)

By moving the For Each loop to the first thing done before anything else (As hinted by @veljkoz), that got rid of the Collection was modified, enumeration may not continue error I was getting when I set csr.CaseSubject = Nothing.

It also turned out to be important to not attach entities (e.g. not to set csr.CaseSubject to an entity but only to Nothing) but instead to use the .SubjectID property. A combination of all the above led me to the following code, which works perfectly and doesn't try to insert duplicate rows.

+1 to @veljkoz for the assist but also note that the resolution includes setting the entity reference to Nothing and using the ID property.

Full, working code:

 Public Function CreateNewCase(c As CAMSModel.Case) As String Implements ICamsService.CreateNewCase    Using ctx As New CAMSEntities        ' Subjects first, otherwise when you try to set csr.CaseSubject = Nothing you get an exception '        For Each csr In c.CaseSubjectsRelationships            Dim spin As String = csr.CaseSubject.CRMSPIN            Dim s As CaseSubject = ctx.CaseSubjects.SingleOrDefault(Function(x) x.CRMSPIN = spin)            If Not s Is Nothing Then                ' The subject has been found based on CRMSPIN so set the subject in the relationship '                csr.CaseSubject = Nothing                csr.SubjectID = s.ID            End If        Next        ' Find the case type '        Dim ct = ctx.CaseTypes.SingleOrDefault(Function(x) x.Identifier.ToUpper = c.CaseType.Identifier.ToUpper)        ' Give an error if no such case type '        If ct Is Nothing Then            Throw New CaseTypeInvalidException(String.Format("The case type {0} is not valid.", c.CaseType.Identifier.ToString))        End If        ' Set the case type based on that found in database: '        c.CaseType = ct        c.CreationChannel = "Web service"        c.CreationDate = Now.Date        ' Save it '        ctx.AddToCases(c)        ctx.SaveChanges()    End Using    ' Return the case reference '    Return c.ID.ToStringEnd Function