チェレプコーフを陥れるためにビジネスマンに変装した警官が仕組んだ囮捜査であったことがやがて明らかになり、逆に沿海地方内務職員に誣告罪が適用された(74)。ところが、エリツィンは同年12月23日、今度は職務怠慢でチェレプコーフを再解任した(75)。チェレプコーフ追い落としの陣頭指揮を執ったのは、この1年後にはナズドラチェンコを裏切ることになるレベヂーネツ副知事であった。
ナズドラチェンコは、チェレプコーフに替わって、コンスタンチン・トルストシェイン(1952年生)を市長代行に任命した。概してナズドラチェンコの「チーム」(副知事(76))は、ナズドラチェンコに敵対する側もその能力を認めざるを得ないサドムスキー(財務担当)、ドゥビーニン(農業担当)、スチェグニー(対外経済関係担当)などのテクノクラート型の指導者と、実行部隊・切込隊とでも呼ぶべき部分から成るが、こんにちトルストシェインは後者の代表であると言われている。「ナズドラチェンコ組」の「舎弟頭」にあたる人物だとみなしてよかろう。ある中立的な現地の高位の観察者によれば、トルストシェインは、2万ドルはしそうな純金の腕時計をし、数千ドルはしそうなベルトをし、「一目でまともでないとわかる」風貌をしているとのことである(77)。建設業界出身のトルストシェインは、職場の共産党委員会書記を経て、1990年、ウラジオストク市ペルヴォレーチェンスキー市区のソビエト議長に選ばれた。エヴレーモフ市長下でそのまま市区行政府長官に任命され、運命の1993年を迎えた。市長選挙に出馬したトルストシェインは、「ポピュリスト」チェレプコーフとは違って、自分が市行政の経験を積んでいることを訴えたが、得票率わずか1.9％で第1回投票で敗れた。彼は後にクライ行政府に移って工業委員会議長を務めていたが、もちろんウラジオストク市への未練を捨たわけではなかった(78)。
市長代行に任命されたトルストシェインは一時的にでもチェレプコーフと共に働いた職員を嫌い、自分の任期を通じて市庁職員のほぼ3分の1(約140人)を更迭してしまった(79)。その反面では、トルストシェインは、市区レベルの指導者に依拠する伝統的な指導スタイルをとった(このことは後に大きな意味を持つことになる)。トルストシェイン下で市庁とクライ行政府の間の関係は当然ながら良好であったが、1995-96年冬頃から深刻化し始めたエネルギー危機に際して、クライ行政府の意を受けてウラジオストク市民に耐久を説いたことは彼の評判を落とした。
1995年12月にナズドラチェンコが知事選挙に圧勝すると、トルストシェインも公選市長になりたいとの願望を表明した。当時はナズドラチェンコ派の権勢の絶頂であったから、1996年の早い時期に市長選挙が行われていれば、おそらくトルストシェインは勝てただろう。しかし、ナズドラチェンコは、沿海地方知事選挙
