More often than not, established companies have immigration lawyers that would much rather have you work with a valid work permit and not under implied status (your application can be returned, after all). That's what happened to us, in any case. They're just being safe.By the way I don't get it how it affects people that are on implied status, if you already had a Work Permit. You can apply and get a job on implied status. (I did it multiple times)