Okay, it seems I found out. Each letter has to be changed to its hexadecimal ASCII representation, using capitals. So to start at 'ABC' or 'Abc', one has to use cmstarthexsortkey=414243. For non-ascii characters, I assume it's the Unicode representation (which for the ASCII set is the same). So far, so good. But it seems there are exceptions to this too - on Dutch, to have the same start, one has to use cmstarthexsortkey=27292B instead. On Russian it does not work at all - 0878087904 starts at the beginning, 08768087905 is beyond the end. On Spanish, Swedish and Italian, 00 is already beyond the end, so you cannot even get the full list this way. It's a mess.

Smashing idea from the Mediawiki developers. Let's deprecate this thing that people use, and force them instead to use this other thing. Oh, and let's not describe anywhere what this other thing is or how it works. Nobody needs that, right?