This paper constructs a Two-Agent New Keynesian model in which the monetary authority implements a zero lower bound interest rate policy to examine whether the paradox of toil is present (i.e., whether a payroll tax cut policy is harmful to mitigating the effects of the Great Recession) during the zero lower bound period. Five notable findings emerge from the analysis. First, when the proportion of the rule-of-thumb (RoT) households is relatively small, the implementation of a payroll tax cut policy will further deepen the Great Recession. Second, when the proportion of RoT households is relatively large, the payroll tax cut policy can be a powerful policy instrument for alleviating the Great Recession. Third, as the evidence reveals a relatively large value of the proportion of RoT households in the U.S. (up to 30%), our numerical analysis calibrated to U.S. data demonstrates that the paradox of toil does not hold. Fourth, in association with either a lower profit share, a larger lump-sum tax share, a lower degree of price stickiness, or a higher probability of the shock remaining in its short run status, an additional payroll tax cut policy tends to generate a lower short-run output multiplier. Fifth, our extensions indicate that the validity of the paradox of toil is closely related to (i) the monopolistic profit and lump-sum tax distributions between RoT and optimizing households and (ii) whether the government balances its budget by levying lump-sum taxes or issuing government bonds.