The classical Liouville property says that all bounded harmonic functions in (Formula presented.), that is, all bounded functions satisfying (Formula presented.), are constant. In this paper, we obtain necessary and sufficient conditions on the symbol of a Fourier multiplier operator (Formula presented.), such that the solutions (Formula presented.) to (Formula presented.) are Lebesgue a.e. constant (if (Formula presented.) is bounded) or coincide Lebesgue a.e. with a polynomial (if (Formula presented.) is polynomially bounded). The class of Fourier multipliers includes the (in general non-local) generators of Lévy processes. For generators of Lévy processes, we obtain necessary and sufficient conditions for a strong Liouville theorem where (Formula presented.) is positive and grows at most exponentially fast. As an application of our results above, we prove a coupling result for space-time Lévy processes.