沖ノ鳥島、南鳥島、択捉島にいった事があるひと

船でコルサコフから国後まで行くという方法もあるようです。

以下最新版Lonely Planet(2000年4月発行)から引用します。
・Kuril Islands - Getting There & Away

This is tricky. About the only way to reach the Kurils is to
fly from Yuzhno-Sakhalinsk, a flight of just over an hour. The
problem is that the islands are often wreathed in a thick fog,
caused by the meeting of hot and cold streams, making airborne
approaches impossible. Although in theory flights are daily,
you have to be prepared to hang around for up to five days
waiting for the weather to improve. An alternative does exist
in sailing. Once or twice a month, a ship departs from Korsakov
, Sakhalin's southern port, taking a day to reach Yuzhno-Kurilsk,
on the southernmost island of Kunashir. It's not a ferry service
but fare-paying passengers are taken - for inquiries contact the
sea terminal in formation desk in Korsakov (Tel 42435-22352) at
pereulok Reydovy 2. A good but potentially expensive contact might
be the director of the Kurilsky Reserve, Yevgeny Mikhailovich
Grigorev (Tel/Fax 42455-21856, magnoliy@sakhalin.ru).

日本から直接ロシアに行くとなると、事前にヴァウチャーを提出する必要が
あり、外務省ともめる可能性があります。
時間があるかたでしたら、バルト3国でビザを取ってからロシア入りするのが
お勧めです。こうした国でビザを取得した場合、ヴァウチャー制度は単なる
名ばかりのものになり、ロシア国内を自由に旅行することができます。実際に
北方四島まで行ってみたわけではないので保証はできませんが、パスポートに
帰国時にスタンプを押すわけではないのでどこに立ち寄ったか、日本側にはば
れようがないはずです。