The negative relationship between inflation and unemployment (also known as the Phillips curve) has been repeatedly challenged in the last decades: missing inflation in 2013-2019, missing deflation in 2007-2010, missing inflation in the late 1990s, stagflation in the 1970s, contrasting with always strong regional Phillips curves. Using data from multiple sources, this paper helps to solve many empirical puzzles by distinguishing between fixed and flexible exchange rate regimes: in fixed exchange rate regimes, inflation is negatively correlated with unemployment but this relationship does not hold in flexible regimes. By contrast, there is a negative correlation between real exchange rate appreciation and unemployment, which remains consistent in both fixed and flexible regimes. These crucial observations have important implications for identifying the source of business cycle fluctuations, for normative analysis, and imply a significant departure from rational-expectation-based solutions to Phillips curve puzzles.