Az 1995-ös Európa-bajnokságon ismét negyeddöntőt játszott, ellenfele ezúttal is a német válogatott volt. 1994. október 9-én otthon 1–0-ra maradt alul a németek ellen, a visszavágón 4–0-ra kapott ki, így 5–0-s összesítéssel kiesett. Mivel az Európa-bajnokság egyben az 1995-ös világbajnokság selejtezője is volt, melynek csak az első négy helyezettje jutott ki a világbajnokságra, így Oroszország nem kvalifikálta magát a tornára.
Az 1997-es Európa-bajnokságra a selejtezőket követően csoportelsőként jutott ki, a tornáról végül szerzett pont nélkül esett ki. Az 1999-es világbajnokság selejtezősorozatában Dánia mögött csoportja második helyén végzett, így pótselejtezőt kellett játszania Finnország ellen. Az oda-visszavágós rájátszásban mindkét mérkőzést 2–1-re nyerte meg, így 4–2-es összesítéssel jutott ki a vb-re. A tornán Norvégia mögött csoportmásodik lett, a negyeddöntőben Kína 2–0-s győzelemmel búcsúztatta az orosz nemzeti csapatot.
A sikerrel megvívott Eb-selejtezőket követően a 2001-es tornán ismét a csoportkör után esett ki. A 2003-as világbajnokság csoportköréből továbbjutva a negyeddöntőben Németországot kapta ellenfélül, melytől 7–1-es vereséget szenvedett, s esett ki. A 2005-ös évre gyengülni látszott az orosz női válogatott annak ellenére, hogy ebben az évben aratta története két legnagyobb arányú győzelmét (május 30-án Izraelt, augusztus 28-án pedig Skóciát győzte le 6–0-ra). A 2005-ös Európa-bajnokság selejtezői során pótselejtező játszására kényszerült, amely során Finnországgal szemben összesítésben 4–1 arányban maradt alul. A 2007-es világbajnokság kvalifikációs sorozatában hiába végzett Németország mögött a selejtezőcsoport második pozíciójában, végül mégsem jutott ki a tornára. Bisztrickij 14 év munka után 2008-ban távozott a válogatott éléről, helyére Igor Salimovot nevezték ki.
A fellendülés a 2009-es női labdarúgó-Európa-bajnokság idejére jött el. A javulás többek között annak is köszönhető, hogy ez idő tájt több olyan játékos is beépült a csapatba, aki tagja volt a 2005-ös U19-es Európa-bajnokságot nyerő válogatottnak. A selejtezőben csoportmásodikként zárt, a pótselejtezőben Skóciát 4–4-es összesítéssel, idegenben lőtt több góllal ejtette ki. A tornáról a csoportkör után búcsúzott, miután szerzett pont nélkül az kvartett utolsó helyén végzett.