I wonder why they asked you to contact Malaysian Immigration directly. The company should do that for you. They'll have to do that for you. It's not like you can approach any country's immigration dept and say "Can I have a work visa? I would like to work in your country."

I'm guessing that when they contact "Malaysian Immigration", they'll be asked to pay all sort of fees.