Warning signs for tipping points (or critical transitions) have been very actively studied. Although the theory has been applied successfully in models and in experiments for many complex systems such as for tipping in climate systems, there are ongoing debates, when warning signs can be extracted from data. In this work, we shed light on this debate by considering different types of underlying noise. Thereby, we significantly advance the general theory of warning signs for nonlinear stochastic dynamics. A key scenario deals with stochastic systems approaching a bifurcation point dynamically upon slow parameter variation. The stochastic fluctuations are generically able to probe the dynamics near a deterministic attractor to reveal critical slowing down. Using scaling laws near bifurcations, one can then anticipate the distance to a bifurcation. Previous warning signs results assume that the noise is Markovian, most often even white. Here, we study warning signs for non-Markovian systems including coloured noise and $α$-regular Volterra processes (of which fractional Brownian motion and the Rosenblatt process are special cases). We prove that early warning scaling laws can disappear completely or drastically change their exponent based upon the parameters controlling the noise process. This provides a clear explanation, why applying standard warning signs results to reduced models of complex systems may not agree with data-driven studies. We demonstrate our results numerically in the context of a box model of the Atlantic Meridional Overturning Circulation (AMOC).