Just apply for an internship in a different European country. That kind of arbitrage is what the EU is for.
Even if this is a possibility, it's not a solution.
Could you expand on that a bit? How is it not a solution? If party A will not pay for your labor but party B will, you would choose to work for part B of course and party A would be rightfully deprived of skilled labor because they are not willing to pay for it. What could be wrong with this situation?
What I mean is that this could be a solution for few people but not for every one.
Looking from a country prospective, expecially an economic point of view, it's not a long term solution if the majority of your students apply for interniship in a foreign country (even if EU).
Europe is not USA, we are not a single federal country but an "alliance" of many countries with different economies, rules, languages and even cultures which are in many cases an obstacle.
If it would be relatively easy for a californania student to apply for an internship in NY, would not be as easy for a polish student to go and take an interniship in portugal for the reasons listed.
In my case (italy) hardly anyone will pay you a cent for your interniship even if you are an engineering, CS or math student.
Often companies (expecially if they are little) here see internship like a way to have free manpower.