I've been to Kamchatka (part of a N Pacific cruise, so no info on flights). Russia is _very_ strict on visas - think: long questionnaire including 10 year history of countries visited, invite from local organisation, personal interview, fingerprints - depending on your nationality. So allow plenty of time for getting one, and consider using a professional visa facilitation company in your own country. Hope that helps!