Ok, since no-one hit this one, I will.
I happened to be in Okinawa on business when I found out from my father (with whom I speak very infrequently) that I had two half sisters in Okinawa. There is alot of story surrounding why I didn't find out about them earlier (which I won't touch on), but I had a day and a half free, so I decided I'd try and track them down and at least leave them an email address or something. I had an address and first names, and that is all I had to go on, so I gave it to the cabby, and with my pidgin Japanese explained my intent. By the way, in Japanese they don't say "half-sister", they say "hara-chigai onee-san".
Anyways, the cabby was really nice and once he understood my intent, he took me all over hell's half-acre trying to find the place. Once we found it, we discovered that it had be abandoned for a long time. I took some pictures and their neighbor came out wondering what was going on. The cabby was nice enough to explain the situation and the neighbor called my half sisters’ mom, and we got the new address. The cabby then took me to their mom's house and she invited me in for tea and showed me pictures of my sisters over the years (I wasn't able to meet them at that point in time), it was quite nice. Now, after 30+ years, part of my father's side of the family tree has been reunited and is in touch with each other again.
So long story short, it isn't impossible, but I'd say just going on family names and not being close relatives might seem be abit むり。
PS: I gave the cabby a huge tip too, he deserved it, lol.
EDIT: All things equal, if you know they live in Okinawa and Tokyo, I would start looking in Okinawa. Its smaller and has less of an in/outflux of people, so I would imagine it would be easier to look there. Also, you'll probably have to do more research to begin with. You will need to find some good contact information/names/starting points. If you can come up with the names of your common great grandparents etc, etc.. it would make it easier.