What it boils down to is that companies are given the opportunity to hire foreigners who are used to much lower salaries under conditions where said foreigners will have lower job mobility. This means that companies have every incentive to hire people more cheaply than they can hire locals. But in order to do so they have to put up a pretense of having tried to hire an American and have to swear up and down that they can't find an American to hire.
In short we're putting pressure on companies to lie and everyone knows it. However it is difficult to demonstrate whether any given company has, and it is very much not in their interest to let accusations of it stand. Is there any wonder that we get conflict over this?
What I would prefer instead is a simple market based solution. Any company wishing to hire a foreigner can upon posting a bond for that foreigner. (To cover expenses if that foreigner poses a problem.) The foreigner has no obligation to their employer - if the foreigner wishes to leave a week after arriving for a better job they are free to, but the original company still is liable for the bond.
Under that system companies have no obligation to claim that they looked for a local. However they have a clear incentive not to hire foreigners. Any company that hires a foreigner regardless is demonstrating by their action that either this foreigner is exceptionally valuable (and therefore is a good addition to the USA economy) or else that there really is a lack of available locals to do this job.