From Vladivostok, Russia to Sakaiminato, Japan
DBS Ferry, a Korean company has a ferry that leaves on Wednesdays to Japan, via Korea. The office in Vladivostok is at Morskoy Vokzal Room No. 239, Nigne-portovaya Str. 1 Vladivostok, 660090. Tel: 7-4232-30-2704/2664 Fax: 7-4232-30-2664. I think this is the sea terminal behind Vladivostok train station.
Entry Procedures (Sakaiminato)
JAF may have to authenticate your carnet (see Entry) before you can go through customs. Go to customs first. If they say you need documents from JAF, you can authenticate your carnet at the Shimane office in Matsue City. See map here. It is best if you fax a copy of your carnet to JAF before arriving in Japan.
The cheapest places to stay in the area are probably the youth hostel or Toyoko Inn in Matsue.
From Sakhalin, Russia
Another ferry goes between Korsakav on Sakhalin Island and Wakkanai in north Japan. It is run by Heart Land Ferry company. You can buy tickets different locations in Korsakav. Midoriyu Rider House is a cheap place to stay in Wakkanai (Google map in Japanese).
Entry Procedures (Wakkanai)
As of 2015, Wakkanai customs asks for a carnet. They used to allow temporary import without one, but this changed due to people leaving their vehicles in Japan.
From Busan, Korea
Ferries from Busan go to Shimonoseki and Hakata (Fukuoka). Take the ferry to Hakata, because there is a JAF office there. There is no JAF office in Shimonoseki. Koreaferry (site in Korean) operates the ferry to Fukuoka.
Entry Procedures (Hakata/Fukuoka)
JAF must validate your carnet (see Entry) before you can go through customs. Be sure to contact JAF before coming to Japan.
The closest JAF office is in Fukuoka city (map in English). Take the subway to Muromi station. The office is a short walk from the subway station.
CAUTION: Vladivostok-Fushiki Ferry is not running any more. Use alternative Vladivostok-Sakaiminato.