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{é}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{é}vy concentration function associated with symmetric distributions.