A szervezet, amelyet a szovjet hatóságok a húszas években kiutasítottak az országból, 1992-ben indíthatta be újra tevékenységét Oroszország területén. Kálváriája 1997-ben kezdődött, amikor az orosz parlament jóváhagyta azt a törvényt, amelynek értelmében 2000. december 31-ig minden, kevesebb mint 15 éve működő vallásos szervezetnek be kell jegyeztetnie magát a helyi hatóságoknál. Az új törvény előírásainak megfelelően az Üdvhadsereg moszkvai irodája 1999 februárjában benyújtotta papírjait a hatóságokhoz. Kérelmük első elutasítását, amely csak hat hónappal később érkezett meg, a hivatalban azzal indokolták, hogy mivel a szervezet főirodája Londonban van, ezért nem kerülhet bejegyzésre, csupán képviseleti irodát nyithat a városban. Kenneth Baillie ezredes, az Üdvhadsereg moszkvai tevékenységének vezetője úgy véli, ez a törvény félreértelmezése. 1999 szeptemberében a szervezet pert indított az egyik moszkvai bíróságon, amely azonban a város javára hozott ítéletet, a fellebbezést pedig ez év november végén elutasították. Baillie elmondása szerint itt az indokok között még az is szerepelt, hogy mivel a szervezet nevében szerepel a hadsereg szó, ezért olyan militarista szervezetnek tekintik, amely az orosz kormány erőszakos megdöntésére készül. A szervezet most a Legfelsőbb Bírósághoz kíván fellebbezni, ehhez azonban a legutolsó döntést írásos formában is meg kell kapniuk. Az Üdvhadsereg ügyvédei azonban a bíróságtól azt a választ kapták, hogy ezt egy hónapon belül vehetik kézhez, ami viszont azt is jelenti, nem biztos, hogy marad elég idejük a december 31-i végső határidő előtti bejegyeztetésre.
Az Üdvhadsereg, amely az Uraltól nyugatra 14 városban tevékenykedik, más régiókban még nem ütközött hasonló problémába. Nem mellékes az sem, hogy a szervezet az 1997-es törvény elfogadása óta már közel 20 ezer dollárt fizetett ki különböző jogi szolgáltatásokért, holott ezt az összeget szívesebben költötte volna saját programjai fejlesztésére.
A vallási törvény által beállított óra azonban tovább ketyeg Oroszországban, s előfordulhat, hogy december 31. után több ezer egyházat kényszerít majd kapui bezárására. Egyes emberi jogi csoportok szerint az ország területén működő mintegy 17 ezer vallásos csoportból eddig mindössze 9 ezernek sikerült magát bejegyeztetnie. A Washingtonban székelő USA Koalíció a Nemzetközi Vallásszabadságért (CIRF) nev? szervezet szerint a hatóságok több csoport bejegyzési kérelmét elutasítot-ták, ezenkívül pedig számos esetben előfordult az is, hogy az állam által favorizált ortodox egyház késleltette a procedúrát, vagy a nem ortodox csoportok kérelmének megtagadását szorgalmazta. Elliot Abrams, a CIRF elnöke leszögezte: rendkívül sajnálatos lenne, ha Oroszországból januárban a vallásszabadság szisztematikus megcsonkításáról érkeznének hírek.