Boy does this hit close to home. I was almost exactly in the same place 2 years back. Dropped out of PhD, start looking around for a gig, then promptly rejected by almost every top IT/telco related Japanese companies.
My solution was similar to @patio11's advice: a) iterate and refine your process, b) hack something on something, anything, on the side, and c) go to the events where networking actually takes place.
All of these will give you both tangible and social proof to bring to table once you eventually get through to the interview round.
Good post, but unfortunately getting hired in Japan involves a lot more aspects than how you answer/ask questions.
For one thing, the process of hiring "fresh college graduates" in Japan is a particular beast of its own, rightly deserving books written about it. As a recent hire here, for the past year I have gone through multiple gauntlets of psych exams, hand-written/online tests, group discussions, test cases, interviews, etc. Here's my tips to increase your chances of getting hired:
1. An introduction/recommendation by someone from the inside trumps everything.
Before even handing in a application, get to know a person from the company that you are going to apply into, preferably someone in a high position. If you went to a Japanese university (especially a high-ranking one), a professor's recommendation is basically gold. At the very least, any employee's introduction (even non-management) will get you past the HR filter and most likely give you the first interview directly with an engineer, where your various social faux pas will be forgiven.
2. Engineering skills aside, employers are concerned about 2 things: a. How good is your Japanese? b. How long are you going to stay in Japan?
How you answer b. is up to your judgment, but you have to be straight-up honest with a. If you ever had any doubts about your Japanese (as I have), just be up-front about it. No sense in bullshitting, as they will figure you out by the first interview anyways. On the other hand, if you did a lot of prep, you will surprise them and exceed their expectations.