First - I don't teach English. However, I think I can give you some advice ...
Unlike other parts of Asia - eg. Taiwan, China, Korea - Japan does not seem to utilize placement agencies for ESL instructors. Instead, many of the larger chain
eikaiwa seem to go direct. Most of the big
eikaiwa chains still recruit stateside:
And, then we have,
Some advice on this site
here and also
here.
And, a list of schools/firms that come recommended but might be off the radar due to their smaller size:
Also, there are companies that send instructors directly to companies to teach. A friend who used to teach indicates you should apply directly. He also said that in the past, they used to bring people over following a telephone interview etc., but nowadays with the economy still in a slump and a relative glut of gaijin instructors, they'll only interview you if you are in-country.