Transaero just announced a direct flight from Moscow to Murmansk. Three times a week, 2.5 hours in the air, and the cost is said to be 6000 roubles ($150 at the current rate) both ways. Another 6 hours of rail to Kandalaksha but still beats 36 hours by train alone.
Kandalaksha+
The City of Kandalaksha, Murmansk oblast, and its vicinity. Getting there, where to stay, what to do. The ultimate source of Kandalaksha and area info in English.
To that add getting from Murmansk to the airport (about 20km), plus all the motions with registration, plus getting from Domodedovo to Moscow. I think another 5-6 hours can be easily added, thus making it 2.5+6+6=14.5. And all that time you jump from vehicle to vehicle. The train is not 36 but 29-30 hours, and all you do is lie down, and it gets you from the city center to the city center. I vote train.