Note: As always, I advise that you seek professional legal and/or labor advice before acting on any opinions given here.
While the recruiting industry typically focuses on the top end of the job market, i.e., the engineering, banking, and management jobs, a much bigger layer of employment and one that most of us have been through is that of "entry-level" jobs. These are provided by vendors of all types who feed into the larger multinationals or who are in a commodity industry, such as English-teaching (whether it should be treated as a commodity is another issue).
There is a place for these companies, and although you see them get vilified on bulletin boards for low wages, without them many people would not be able to accumulate the necessary track record to be considered for positions in larger companies. One sector that I'm very aware of is the IT industry, where many of the larger, more prestigious firms, including banks, securities firms, logistics companies, IT consultancies, etc., actually prefer to receive their future employees from entry-level vendors, because then the candidates are proven performers.
The problem for entry-level employers is whether or not they can make a reasonable profit from the new employee before the economics of the market kick in and the person is offered a higher-paying job somewhere else. In one of my companies, which take on a lot of entry-level people, we use an honor system whereby we ask the candidate to do the right thing and stay two years. Most people do the right thing and if by the end of that period we're not paying them enough to stay, we wish them the best of luck and facilitate their move onwards. Such is life and I'm a strong believer in what goes around comes around - that is, many of these people eventually rise through the ranks of a larger firm and eventually become my customers.
But all IT vendors do not hold this ideal of a long-term ecosystem, and in some other sectors it just plain doesn't work. Again English teaching comes to mind. For these companies, then, holding on to entry-level people and extracting some value is enacted by way of strict employment contracts. These contracts can be really tough, threatening dire repercussions and penalties if the person leaves before the contract ends. The question is: is this allowed?
The Japanese constitution guarantees the right to work, and it doesn't say that foreigners should be treated any differently. The government takes this right very seriously, and indeed for many decades until the 1990's made itself the only legal recruiting entity, so as to guarantee people fair and equal treatment in their job search. Likewise, the government has passed labor laws, which protect this constitutional right, and thus everyone working legally in Japan has the right to move from one employer to the next as they wish. Contracts between an employer and employee that contravene this constitutional right are not legal.
So why do some employers persist in writing such contracts? Firstly, they are hoping that the person signing the contract is unfamiliar with the law and won't challenge it. Secondly, they are allowed to write in clauses that achieve the effect of holding on to you, and yet not violate the law. For example, it is legal for them to require that before leaving you pay back any educational or training expenses, also any loans, subsidized apartments, etc. If they have you on a financial hook and you're not able to pay them back quickly, this acts as a guarantee to stay. Also, they can time your bonuses so that you can only collect them if you renew your contract. And lastly, they can withdraw sponsorship of your working visa.
Further, if you're a senior manager or a director, then the restrictions in a job contract about how and when you can move actually can be enforced. This is because you are no longer regarded as an employee but rather more like a "partner" in the business and the issue of trust and fiduciary duty start to have more influence than labor law rights.
What can you do if you have signed a contract that effectively prevents you from moving to another job? Firstly, you should get advice, either from your labor standards office or from a lawyer. Secondly, before you notify your intention to move, make sure you have another employer lined up with a signed job offer. Once they sign that job offer they have a contractual responsibility to hire you, and this gives you some foundation for dealing with your existing employer and their contract.
Lastly, I'll note that unless you have broken some other law, in practice the Immigration people are not going to throw you out of Japan if they know that you already have your next job offer lined up. They know that productive foreign taxpayers are good for the economy. So a company sponsoring your visa and threatening to tell immigration if you leave is making nothing more than a hollow threat.