I want to switch locations to a different country, but I don't have any job offer and I don't know where to start, I know that some companies will sponsor visas for skilled workers, but I'm not sure whether I should contact a recruiter agency in other country given that at this moment I don't have the legal status to work. In general terms, does the recruiters show interest in these type of situations where they have to accommodate you with a company that would sponsor a visa or I would be wasting my time?
My suggestion would be to review a few different routes that may get you where you want to be:
1) If you have friends or family in that different country, it may be worth asking them if they know companies that are looking for workers in your field and would be willing to sponsor a foreigner in for the job. Your current employer and co-workers may also be useful here to consider. The idea here being about working around bureaucracy.
2) Consider what networks may have connections of jobs in those places. In my own case, I went from Canada to the US because of a job posted in my university's career services section. What schools, associations or other organizations may be able to help you apply for what positions?
3) International recruiters. This can work if you have the experience with a specific skill set that is highly sought. Part of this comes from posting your resume on various large sites within that country and then seeing recruiters call you so that they come to you rather than you go to them.
Something to keep in mind is that you will have to have some kind of story for the, "Why would you want to move to X?" that could well be asked since some companies may question why you want to make this move.
My guess would be that it would only be worth it if you have skills that are very, very hard to find. Otherwise, most tech recruiters (at least in the US) tend to think more like sales people. They don't see it as a matching problem. They see it as a matter of finding leads. If there's any reason you'll be rejected by a company, they don't want you in their lists of employees to spam at their lists of employers. I would say focus on finding companies that are willing to help you with the legal status issue first and recruiters second.
I would suggest that getting a job internationally at the moment is likely to be very hard - unemployment in many countries is still very high, and this tends to lead to tighter immigration controls.
In our case (we're NZ based, and highly specialised) I can advertise directly internationally for roles above a certain pay grade (which is higher than the median national wage) - my firm had to be certified to allow this to happen - BUT I am still obliged to consider NZ residents that match the job description and ideal candidate specification before any non-resident. Immigration check this carefully.
As someone who recruits, I generally prefer local candidates over those I have to relocate. Typically the process can take more than three months for the various police and medical checks, and can easily be derailed in that time by lifestyle changes.
To give you an idea, I have not had to relocate someone from overseas for the last 4 years, as there has been a local (or returning Kiwi) candidate that matched what we needed every time.
If you are serious about moving to another country then working with an immigration agent based in that country is a much better idea than a recruitment agent; depending on skills, experience and the country you may be able to get a visa type that allows you to travel to the country to seek work, which of course is a lot easier.