European migration policies are characterised by a fundamental paradox: they are getting tighter and tighter just while public opinion is becoming more favourable to migrants and the immobility of European citizens expands the scope for spatial arbitrage, accruing the benefits, of immigration. In this paper we consider two possible explanations for this puzzle. At first, based on a computable general equilibrium model, we evaluate whether migration to "rigid labour markets" a-la European involves cost, which are neglected by economic theory. Our results suggest that the economic benefits from international migration are, at a GDP gain of 0.2-0.3% at a migration of 1% of the labour force, but that natives in the receiving countries may lose out especially when generous unemployment benefits are provided to the migrants. Then, we evaluate effects of co-ordination failures in the setting of national migration policies, documenting that a race-to-the-top in migration restrictions has indeed occurred in the case of the Eastern Enlargement of the EU and has involved significant diversion of migration from more restrictive to less restrictive countries. Finally we discuss two potential ways to invert the trend towards stricter barriers to migration, namely i) restricting access to welfare and ii) adopting an EU-wide migration policy.