Paul would like to eliminate the cap. But this makes the first problem worse. If you solve the first, then removing the cap makes perfect sense.
So how do we solve the first? My proposal is that any company wanting import an employee can, but has to post a significant bond for the cost of deporting the employee if there are problems. That immigrant is free to transfer employment. At the end of a year, if that immigrant left to go to another company, the original employer loses the bond and owes the difference between the immigrant's current income and the original one.
Under this proposal there is a disincentive to bring in an immigrant unless said immigrant really is paid above market rate for their skills. Locals may not like the competition, but people will be hiring immigrants because they think they are better, and not because they are cheaper than the market.