Говорят можно через агенство сделать временную регистрацию за 2000 рублей. У меня подруга сейчас себе делает.
И есть организации, которые имеют законное право принимать на работу иногородних. И соответственно имея на руках документ от фирмы, что она будет там работать, ей сделают санитарную книжку по мед. полису(который также предоставляется фирмой).
Просто долго и не легко искать.