First, the non-relativistic equation
$$ E= mc^2 + \frac{mv^2}{2} $$
is equivalent to its second power,
$$ E^2 = (mc^2)^2 + mc^2 v^2+ \frac{m^2v^4}{4} $$
If $v/c\ll 1$, then the last term is much smaller than the previous two, and the first two terms on the right hand side are equivalent to the correct relativistic
$$ E^2 = (mc^2)^2+ (pc)^2 $$
which completes the proof that the two formulae are the same in the $v/c\ll 1$ limit.

The first, relativistic formula is always right. The second one, if we want to consider "only absolutely correct and exact" formulae, is never correct – except for the case $v=0$. However, the non-relativistic equation may be written in a completely rigorous way (to describe that it is approximate) as
$$ E = mc^2 + \frac{mv^2}{2} + O(mv^4/c^2) $$
The symbol $O$ represents "a function that in the relevant limit, here $v/c\to 0$, has a finite limiting ratio with the function in the parentheses after $O$", and this concept may be and is defined 100% rigorously.

The boundary of the values of $v$ where the non-relativistic formula applies is indeed "fuzzy" – one can't quote any exact value of $v$ (except for $v=0$, in the useless sense described above) where the non-relativistic formula ceases to hold. But for $v/c\lt 0.1$ or so, the error is smaller than one percent. For greater speed than $v=c/2$, the non-relativistic formula becomes so bad that it can't be use in any quantitative context.

The error of the non-relativistic energy formula – or, more democratically, the difference between the two formulae – simply *gradually* increases from $0$ at $v=0$ to something comparable to 100% at $v=c/2$ and a huge error for $v\to c$.

Physics is fundamentally based on continuous numbers which means that pretty much all of its quantities are gradually changing and their differences and errors are gradually changing, too. Also, errors smaller than a certain threshold are experimentally undetectable which allows one to say, in a very specific empirically rooted sense, that the error is basically zero.

Because of the omnipresence of limits and limiting claims about formulae, expressions, and theories in physics, one may say that if you won't comprehend and embrace these important concepts about limits and expressions' being equivalent in limits, you have virtually no chance to understand *anything* in physics.