There is a passenger ferry (not Star Cruises) that doubles as a cargo vessel making a regular circuit Taiwan-Okinawa. It usually goes from Naha-Keelung-Kaohsiung-Naha, but there are variations (sometimes stops in Ishigaki). You have to call ahead with your dates in mind to find out. I recently went from Kaohsiung to Naha for 4500 NT. It only took 24 hours!! And we were travelling at about 30 km per hour…so Okinawa and Taiwan are much closer than they look on political maps. Here are the agents in Taiwan: Yeong An Maritime Co. in Taipei 02-2771-5911 or Hai Tien Shipping in Kaohsiung at 07-3309-811. PM me if you are coming and I will meet you at the ferry terminal.