$x[n] = c^n * u[-n-1]$
Where u[n] is Heaviside step function. According to Matlab and WolframAlpha this equals 0.
However if I compute the sum according to the z-Transform definition I got (sum from -$infinity$ to -1 and then shifted to 1 to $infinity$)
$X(z) = c^{-1}*z + c^{-2}*z^2 + c^{-4}*z^4 + .... + $
Which converges for c<1. Where is the failure?
The reason why the result equals zero is that Wolfram Alpha uses the unilateral $\mathcal{Z}$-transform defined by
$$\mathcal{Z}\{f(n)\}=\sum_{n=0}^{\infty}f(n)z^{-n}\tag{1}$$
as detailed here. Since your sequence equals zero for $n\ge 0$, its unilateral $Z$-transform is obviously zero.
The bilateral $\mathcal{Z}$-transform of the given sequence exists and it is given by
$$\mathcal{Z}\{f(n)\}=\frac{z}{c-z},\quad|z|<|c|\tag{2}$$
Note that convergence of the bilateral $\mathcal{Z}$-transform depends on the magnitudes of $z$ and $c$, and it cannot only be determined by the value of $c$, as suggested in your question.