While taking a brute-force look at this question I discovered that it seems that almost every prime (I'll conjecture every prime larger than 20627) can be written as $p=w^2+wc+d$ for $w,c,d\in \mathbb{Z}^+$ and with $cd$ a perfect cube.
This can be rearranged to say that for almost any $p$ there is a positive integer $a such that the equation $ y^2=x^3+\frac{1}{4}+\frac{p}{a^2} $ has a solution of the form $(x,y)=(-u/a,v/(2a))$ where $u,v\in \mathbb{Z}^+$. (This is slightly weaker, to yield the form for $p$ above we also need $a\mid u^3$ and $v\equiv a\pmod{2}$.) This looks like a variation of seeking integer points on a Mordell curve, but allowing solutions on a finer grid. It might be a more difficult way of looking at the problem, but does it seem like some theory of elliptic curves could help classify when there's a solution (in general, or say given $a=1$ or $a=2$)? Or, given that there is a solution for $a=1$, does this suggest an algorithm for finding it?