About Recruiters
I contacted a few recruiters from Australia before I went to Japan. The ones that said anything all said the same thing: it would be much easier to look for a job while over there. This is true even for the recruiting firms that have branches in both Japan and Australia; they seem to operate pretty much independently.
There are enough workers already in Japan that companies do not generally have to consider people who are not yet in the country. Unless you are in Japan and available for interviews, it will be very hard to get any employer or recruiter interested in you.
Some companies present themselves as recruiters, but are really more like contracting companies, hiring you and selling your services to a third party. I don’t know what difference this might make to your visa status, but it probably reduces your salary, since the contracting company will be taking a cut. One agent I dealt with did not tell me this until I was on the way to an interview; the agent told me to be on my best behaviour for the interview because I was representing his consulting company!
It’s best to make sure you understand exactly what the terms are before signing up.