  The recurrence features of persistent random walks built from variable length
Markov chains are investigated. We observe that these stochastic processes can
be seen as L{\'e}vy walks for which the persistence times depend on some
internal Markov chain: they admit Markov random walk skeletons. A recurrence
versus transience dichotomy is highlighted. We first give a sufficient Fourier
criterion for the recurrence, close to the usual Chung-Fuchs one, assuming in
addition the positive recurrence of the driving chain and a series criterion is
derived. The key tool is the Nagaev-Guivarc'h method. Finally, we focus on
particular two-dimensional persistent random walks, including directionally
reinforced random walks, for which necessary and sufficient Fourier and series
criteria are obtained. Inspired by \cite{Rainer2007}, we produce a genuine
counterexample to the conjecture of \cite{Mauldin1996}. As for the
one-dimensional situation studied in \cite{PRWI}, it is easier for a persistent
random walk than its skeleton to be recurrent but here the difference is
extremely thin. These results are based on a surprisingly novel -- to our
knowledge -- upper bound for the L{\'e}vy concentration function associated
with symmetric distributions.
