We prove the existence of complex polynomials $p(z)$ of degree $n$ and $q(z)$ of degree $m<n$ such that the harmonic polynomial $ p(z) + \overline{q(z)}$ has at least $\lceil n \sqrt{m} \rceil$ many zeros. This provides an array of new counterexamples to Wilmshurst's conjecture that the maximum valence of harmonic polynomials $p(z)+\overline{q(z)}$ taken over polynomials $p$ of degree $n$ and $q$ of degree $m$ is $m(m-1)+3n-2$. More broadly, these examples show that there does not exist a linear (in $n$) bound on the valence with a uniform (in $m$) growth rate. The proof of this result uses a probabilistic technique based on estimating the average number of zeros of a certain family of random harmonic polynomials.