I think the easiest way to fix the problem is to do exactly what you suggest -- decouple a person's immigration status from their employer. I'd do this by scrapping the H1B program and instead simply offer a green card to every person that has a letter of employment from a US company. The government could continue to apply various filters (total quotas, country-specific quotas, educational or experience requirements, language competency, etc). [1] However, at soon as a person is admitted to the US, their immigration status should have absolutely nothing to do with their employer.
Under this system, a company can't pay an immigrant less than their worth, since the person is free to work at any business that is willing to pay more. It also fixes a whole bunch of other subtle problems that come up with an employment-based immigration system.
For example, right now once a H1B holder applies for a GC, they can neither changes companies nor change their job title (e.x. be promoted) without abandoning their GC application. Since this process can take years and thousands of dollars, immigrants are not only shackled to their sponsoring company, but to a particular job (and often pay-level) within that business.
I should point out here that I'm Canadian that may one day be working in the US... so perhaps I have a bit of a pro-immigrant bias here.
[1] Personally, I'd get rid of most of these too, but that is the subject of a different rant.