Thank you for the suggestion. I did not try it with escaped characters. That would probably work. However, our data is already in place using Unicode code points in our xpaths and we need this new code to be backward compatible.
I did open a bug with TAC and Tail-f has responded that they acknowledge the bug in Maapi.queryStart().
In the meantime, I think I have found a workaround by using Maapi.newCursor() and Maapi.getNext() to iterate over xpaths with Unicode code points and putting them in a TreeMap to sort them. (I had previously relied on the sorting capability provided by Maapi.queryStart).