As far as I can see the problem is in Debian fontconfig priorities/rules?
On more-or-less fresh system I get:
pent@sol:~$ fc-match monospace:lang=ru_RU
n022003l.pfb: "Nimbus Mono L" "Regular"
After installing Liberation I get:
pent@sol:~$ fc-match monospace:lang=ru_RU
DejaVuSansMono.ttf: "DejaVu Sans Mono" "Book"
It seems really strange that Numbus got higher than say FreeMono which is system default. I'm not sure I can even submit a helpful bug report as I have very weak understanding about how fontconfig is supposed to work :-/
Anyway, Emacs "must be above suspicion".