It is clear that $p_1^\mu+p_2^\mu=0$ if and only if
$$
E_1+E_2=0\qquad\text{and}\qquad \vec p_1+\vec p_2=\vec 0
$$
OP correctly argued that $\vec p_1+\vec p_2=\vec0$ is perfectly possible, and asks whether $E_1+E_2=0$ is possible as well. The answer is yes. The origin of energies is irrelevant, and therefore if $E_1+E_2=\mathcal E_0$, it suffices to redefine $E_i\to E_i-\mathcal E_0/2$ to obtain $E_1+E_2=0$.
One could argue that the choice of origin we made above is not natural. If you choose, instead, the origin of energies such that $E=m$ when the particle is at rest, then $E=\sqrt{\vec p^2+m^2}$ is positive-definite. The sum of two positive-definite functions is also positive-definite, and therefore $E_1+E_2>0$, strictly. In that case, the sum of energies cannot vanish.
Finally, if you use massless particles (which have no rest frame), then $E=|\vec p|$, which is semi-positive definite. The only way to get $E_1+E_2=0$ is that $E_i=0$, that is, that $\vec p_i=\vec 0$. But a particle with no mass, no momentum, and no energy, is not really a particle at all: it is the vacuum. Whether this qualifies is a matter of opinion.
To clarify a misconception in the OP: anti-particles have positive energy. The expression $E=\sqrt{m^2+\vec p^2}$ is valid both for particles and anti-particles.