it is possible to get one-or-two-day tourist visa in Kirkenes in a tourist office Bennet BTI, tel. ++/78-992-860, with booking 7-10 days in ahead, or you pay an extra charge. For more than two days obtain russian visa in their embassy in Germany. I was not there but on my way to NorthCape in summer 2001 that was one of basic ideas, so I get this info from a biker in Kirkenes.
AnteK, XTZ 660