Where does randomness help when deciding algebraic geometry over $\mathbb{C}$?
For the question of when does $p=0 \Rightarrow q=0$, randomness can indeed help, as follows. First, factor $p$ (uses randomness when $p$ is given as a straight-line program; doesn't need randomness if $p$ is given as a coefficient vector). Let $\tilde{p}$ denote the square-free version of $p$ - that is, if $p=p_1^{k_1} p_2^{k_2} \dotsb p_\ell^{k_\ell}$ then $\tilde{p} = p_1 p_2 \dotsb p_\ell$. Then $q=0$ follows from $p=0$ iff $\tilde{p}$ divides $q$, which happens iff $q$ is of the form $q=p_1^{k'_1} \dotsb p_\ell^{k'_\ell} f$ with all of the $k'_j$ strictly positive. The latter can be checked by factoring $q$ (uses randomness, as before).
For the general question of $p_1=\dotsb=p_k=0 \Rightarrow q=0$, randomness seems not to help from the complexity perspective, as this problem is $\mathsf{EXPSPACE}$-complete (randomness may help in practice though...). 
For the problem of telling whether the variety $\{\vec{x} : p_1(x)=\dotsb=p_k(x)=0\}$ is empty or not (for polynomials given by a list of monomials and coefficients - which is "sparse but not succinct", that is, not SLPs), randomness also seems to help: assuming GRH, this problem is in $\mathsf{RP}^{\mathsf{NP}}$ by a result of Koiran. It is $\mathsf{NP}$-hard, and not known to be in $\mathsf{P}^{\mathsf{NP}}$.