Ahh, I guess I know the problem:
* texlive-fonts-recommended ships the original URW fonts
* ghostscript-fonts ships the fonts where cyrillic characters
are added
That has for long been a specific change of Debian, and was not endorsed
by URW. Thanks to recent activity from various sides, thje official
URW distribution now also contains cyrillic characters (AFAIR), but
TeX Live is not updated (not when it was frozen, and nor is it now).
But unfortunately it seems that fontconfig returns the TeX Live font
instead of the ghostscript font, thus breaking Cyrillic.