It used to indeed be the case that in Belgium to fire someone the notice period could be quite literally years. However, Belgium changed its laws in 2014. For firing someone it's now 1 week the first 3 months, and then it goes up more slowly. For example, for someone who's been there 4 years it is a 3 month notice period.

As for free movement of labor inside the EU, it is mostly irrelevant how easy it is because of cultural barriers. People don't want to work in a region where they don't speak the language. See for example how workers in Belgium mostly do not cross the language boundary between north and south, despite having an identical legal regime. Europe's polyglot nature makes it quite literally impossible to match the U.S. or China wrt the movement of labor.