Do you have the correct font installed?

installed where? Let me show you the problem with pictures.

It still depends on the font that you use. The images you posted tell me that the font causing the problem has accented characters in its higher-numbered half rather than Russian characters.

Are there embedded fonts used in those PDF files that map on the 8 bit ASCII plane?

Yes there are embedded fonts which use the 8-bit code-page Windows-1251. And if it is going to help here is the code which converts the character codes from ASCII to cp1251:

"1253,'Descent'=>-236,'CapHeight'=>729,'Flags'=>32,'FontBBox'=>'[-24 -218 958 924]','ItalicAngle'=>0,'StemV'=>70,'MissingWidth'=>800); $up=-133; $ut=20; $cw=array( chr(0)=>800,chr(1)=>800,chr(2)=>800,chr(3)=>800,chr(4)=>800,chr(5)=>800,chr(6)=>800,chr(7)=>800,chr(8)=>800,chr(9)=>800,chr(10)=>800,chr(11)=>800,chr(12)=>800,chr(13)=>800,chr(14)=>800,chr(15)=>800,chr(16)=>800,chr(17)=>800,chr(18)=>800,chr(19)=>800,chr(20)=>800,chr(21)=>800, chr(22)=>800,chr(23)=>800,chr(24)=>800,chr(25)=>800,chr(26)=>800,chr(27)=>800,chr(28)=>800,chr(29)=>800,chr(30)=>800,chr(31)=>800,' '=>282,'!'=>287,'"'=>278,'#'=>769,'$'=>565,'%'=>877,'&'=>694,'\=>144,'('=>264,')'=>264,'*'=>500,'+'=>833, ','=>282,'-'=>322,'.'=>282,'/'=>278,'0'=>556,'1'=>556,'2'=>556,'3'=>556,'4'=>556,'5'=>556,'6'=>556,'7'=>556,'8'=>556,'9'=>556,':'=>278,';'=>278,'<'=>584,'='=>584,'>'=>584,'?'=>556,'@'=>1015,'A'=>667, 'B'=>667,'C'=>722,'D'=>722,'E'=>667,'F'=>611,'G'=>778,'H'=>722,'I'=>278,'J'=>500,'K'=>667,'L'=>556,'M'=>833,'N'=>722,'O'=>778,'P'=>667,'Q'=>778,'R'=>722,'S'=>667,'T'=>611,'U'=>722,'V'=>667,'W'=>944, 'X'=>667,'Y'=>667,'Z'=>611,'['=>278,'\\'=>278,']'=>278,'^'=>469,'_'=>556,'`'=>333,'a'=>556,'b'=>556,'c'=>500,'d'=>556,'e'=>556,'f'=>278,'g'=>556,'h'=>556,'i'=>222,'j'=>222,'k'=>500,'l'=>222,'m'=>833, 'n'=>556,'o'=>556,'p'=>556,'q'=>556,'r'=>333,'s'=>500,'t'=>278,'u'=>556,'v'=>500,'w'=>722,'x'=>500,'y'=>500,'z'=>500,'{'=>334,'|'=>260,'}'=>334,'~'=>584,chr(127)=>800,chr(128)=>800,chr(129)=>800,chr(130)=>194,chr(131)=>565, chr(132)=>338,chr(133)=>1000,chr(134)=>500,chr(135)=>500,chr(136)=>500,chr(137)=>1315,chr(138)=>465,chr(139)=>308,chr(140)=>1090,chr(141)=>800,chr(142)=>800,chr(143)=>800,chr(144)=>800,chr(145)=>194,chr(146)=>194,chr(147)=>338,chr(148)=>338,chr(149)=>590,chr(150)=>500,chr(151)=>1000,chr(152)=>500,chr(153)=>833, chr(154)=>389,chr(155)=>308,chr(156)=>1088,chr(157)=>800,chr(158)=>800,chr(159)=>479,chr(160)=>282,chr(161)=>287,chr(162)=>565,chr(163)=>565,chr(164)=>606,chr(165)=>565,chr(166)=>500,chr(167)=>500,chr(168)=>576,chr(169)=>833,chr(170)=>473,chr(171)=>456,chr(172)=>833,chr(173)=>322,chr(174)=>833,chr(175)=>500, chr(176)=>329,chr(177)=>833,chr(178)=>373,chr(179)=>373,chr(180)=>500,chr(181)=>542,chr(182)=>500,chr(183)=>282,chr(184)=>529,chr(185)=>969,chr(186)=>455,chr(187)=>456,chr(188)=>879,chr(189)=>879,chr(190)=>879,chr(191)=>463,chr(192)=>667,chr(193)=>667,chr(194)=>667,chr(195)=>611,chr(196)=>812,chr(197)=>667, chr(198)=>1023,chr(199)=>667,chr(200)=>728,chr(201)=>728,chr(202)=>667,chr(203)=>673,chr(204)=>844,chr(205)=>719,chr(206)=>778,chr(207)=>719,chr(208)=>667,chr(209)=>722,chr(210)=>611,chr(211)=>650,chr(212)=>936,chr(213)=>667,chr(214)=>741,chr(215)=>648,chr(216)=>828,chr(217)=>850,chr(218)=>897,chr(219)=>872, chr(220)=>667,chr(221)=>722,chr(222)=>1032,chr(223)=>702,chr(224)=>556,chr(225)=>556,chr(226)=>522,chr(227)=>430,chr(228)=>602,chr(229)=>556,chr(230)=>837,chr(231)=>500,chr(232)=>567,chr(233)=>567,chr(234)=>510,chr(235)=>557,chr(236)=>618,chr(237)=>558,chr(238)=>556,chr(239)=>557,chr(240)=>576,chr(241)=>500, chr(242)=>496,chr(243)=>500,chr(244)=>912,chr(245)=>500,chr(246)=>578,chr(247)=>520,chr(248)=>692,chr(249)=>712,chr(250)=>734,chr(251)=>690,chr(252)=>552,chr(253)=>500,chr(254)=>758,chr(255)=>543); $enc='cp1252'; $diff=; $file='FreeSans.z'; $originalsize=17904; ?>"

P.S. chr(code) is a PHP function which recieves ASCII code and returns the character(string).