Here, state I is just one closed string going along the path. State III will be used for two strings on the same path - which is called I in the question. Sorry for the permutations: I also discussed a more trivial issue and I don't want to delete it. ;-)
The states I and II are always distinct and there is no non-locality implied by this fact.
In particular, strings usually carry a charge with respect to the B-field - a two-form field in the NS-NS sector; among the 5 ten-dimensional superstring theories, type I theory is the only exception because its string are unoriented. If the path in I,II goes around a non-contractible circle in spacetime, the charge will manifest itself as a "winding number" $w$ - the configurations I,II will have winding numbers $w=1,2$, respectively, and those values of $w$ will behave as different values of electric charges.
The configuration II simply carries twice as high a charge than the configuration I and is completely different - just like two point-like W-bosons on top of each other are different from one W-boson. In fact, the string example of yours only differs by an added dimension to the strings' shape.
It is not hard to agree that two W-bosons on top of one another are different from one W-boson. Would you agree that one doesn't need any non-locality to deduce this fact? The configurations of strings I,II differ at each point along the string, not just globally.
Also, your more general point is totally valid: the interactions of strings are totally local in space as long as we look at strings as extended objects, and the right world sheet theory describing these interactions is also completely local on the world sheet. This condition requires that two interactions (processes) where strings are rearranged locally in some region must always have the same amplitude regardless of what the strings in both cases are doing away from the interaction point.
What you wanted to distinguish in the question was your configuration II and another configuration III (you called I) which has two coincident strings closing around the same path. The configurations II and III may be very hard to distinguish, indeed - in some sense, II is a bound-state version of III.
In the context of matrix string theory, II is a "long string" while III is a pair of strings - and these two configurations may be continuously connected on the configuration space of a Yang-Mills description of perturbative string theory which is what matrix string theory really is:
http://arxiv.org/abs/hep-th/9701025
http://arxiv.org/abs/hep-th/9703030
The configurations II, III only differ by a global monodromy of the matrix theory's gauge field along the long path in space that the strings are wrapped around: the configuration III involves a permutation of the two strands while the configuration II doesn't. The permutation group $S_N$ is embedded into the gauge group $U(N)$ with the same value of $N$ in the context of any matrix-theory model.
In matrix string theory, all closed-string-like (crossing-over) interactions in string theory are represented by the addition of a transposition to the permutation that remembers the monodromy. Such a transposition may occur whenever the points of several strands are close to each other in the physical spacetime and may be described as the DVV interaction - see the 2nd paper above for details. Once we study it rationally, it is counterproductive to draw the strings in a singular configuration. The same mechanism is really taking place whether or not the remainders of the strings coincide.
Recall that the $U(N)$ gauge group arises from D-branes - the fundamental strings as modeled by matrix string theory are really D1-branes which are dual to them, and which appear in a particular extreme kinematic regime: the duality is the pillar of a derivation of matrix string theory (by Seiberg). At any rate, the comments about the differences between II and III really apply to D1-branes, too (or especially to them).
Matrix string theory is discussed here on physics stack exchange:
Good introductory text for matrix string theory