Okay, I played with it a little bit more, and here is what I found:
The first non-Latin character you type into QS will only be used to
match catalogue items that have the lowercase version of that
character. The second character will match anything with lowercase or
uppercase versions of the character.
Here is an example using Greek characters, but it will work the same
with Cyrillic and others:
Say I have three files named Δηρα_Ζω1, δηρα_ζω2, and δηρα_Ζω3. If I
start my QS search by typing a delta (lowercase δ, uppercase Δ), only
the last two files will be found, even though all three files start
with a delta. This is because the first file has a capital delta.
However, if I start my search by typing an eta (η), all three files
will be found. Moreover, after I type an eta, I can type a zeta
(lowercase ζ, uppercase Ζ) and all three files will still match, event
though some files have an uppercase zeta.
What this means for you, Iwan, is that until someone fixes this bug,
you can work around it by starting your searches using the second
character is a contact's name instead of the first character. So if
you are looking for Ландыши, try typing андыши. It is annoying, I
know, but it is the best we can do for now.