What kind of companies might be able to provide visa for foreigners?

J, you have this all backwards and you are accelerating the myth that you first get a permit to work and then go looking for a job. No such thing!

There is no visa company that provides a visa to people. The work pass is applied for by the company hiring you for a job, and the government provides the visa. In the visa it is written the company you are attached to and as such, you cannot use that work pass to work for anyone else. So, your task is to first find the job, and therefore the company willing to hire a foreigner AND apply for (and pay for) a work pass for you. Depending on the job, the approximate costs range from about RM1600-5000 and are good for two years at which time your employer applies again for another 2-year work pass. The rule is a foreigner can stay up to 10 years. (Sometimes, at least I have heard of it, the foreigner has paid the employer for the costs as an incentive for them to hire the foreigner).

The problem or challenge is finding a company that likes you enough to go to the trouble and cost. Can they fill the job with a local person? They would certainly first try, and also they must convince the government that there is no local person who can do this job and so they must have you.

Foreigners have repeatedly asked in the forums for a "general work permit" that would allow them to stay in the country and search for jobs but there is NO SUCH THING.

Last point, the rule is that you apply for the job from outside the country, then the employer imports you. If you are already here and apply for a job, the government may or may not allow it, they may ask you to first go back to your home country and start over. This is not a fixed thing but thats the rule, anyway.

First find the job, then go from there. The work pass comes after they have agreed to hire you so dont worry about that part right now. Get the job first. Good luck.