We analyze determinacy and stability under learning (E-stability) of rational expectations equilibria in the Blanchard and Galí (2006, 2008) New-Keynesian model of inflation and unemployment, where labor market frictions due to costs of hiring workers play an important role. We derive results for alternative specifications of monetary policy rules and alternative values of hiring costs as a percentage of GDP. Under low hiring costs - a typical part of the U.S. calibration - for policy rules based on current period inflation and unemployment our results are similar to those of Bullard and Mitra (2002). However, we find that the region of indeterminacy and E-instability in the policy space increases with the hiring costs. So, higher hiring costs - consistent with the European 'sclerotic' labor market institutions - seem to play an important part in explaining unemployment instability. Under lagged data based rules the area where monetary policy delivers both determinacy and E-stability shrinks. These rules perform worse according to these two dimensions when hiring costs go up. Finally, under expectations-based rules - unlike Bullard and Mitra (2002) - an additional explosive region is introduced. Here also the scope for determinacy and E-stability oriented monetary policy decreases. Interestingly - under the same rule and European 'sclerotic' labor market institutions we find that responding too much to expected inflation and too little to expected unemployment may very well be self-defeating. When hiring costs are large, a central bank that follows such a policy rule could very easily end up in the worst-case scenario of both indeterminacy and E-instability.