If correct sorting is so important in your problem, just use ordinal string comparison instead of culture-sensitive. Only this one guarantees transitive and antisymmetric comparing you want.
What MSDN says:
Specifying the StringComparison.Ordinal or
StringComparison.OrdinalIgnoreCase value in a method call signifies a
non-linguistic comparison in which the features of natural languages
are ignored. Methods that are invoked with these StringComparison
values base string operation decisions on simple byte comparisons
instead of casing or equivalence tables that are parameterized by
culture. In most cases, this approach best fits the intended
interpretation of strings while making code faster and more reliable.
And it works as expected:
Console.WriteLine(String.Compare(x, y, StringComparison.Ordinal)); // -12309
Console.WriteLine(String.Compare(y, x, StringComparison.Ordinal)); // 12309
Yes, it doesn’t explain why culture-sensitive comparison gives inconsistent results. Well, strange culture — strange result.