The key in the index is unique the Unicode standard is supposed to define the order. I was rather hoping I could depend on that, since it is supposed to be a standard.
Looks like my options are:
I could use the ordinal value of the characters and do a numeric sort instead of a textual sort. That's what I was suggesting in point 2 above.
The only other option is to ditch my Perl index creation and rewrite it in C# so that the index creation and the index usage are both using exactly the same sorting library. Not sure I want to go there yet, though.