There are a couple of problems here. First is the complaint that massless particles shouldn't have momentum because "intuition". That's just Newtonian intuition. If you have had quantum intuition, you would think "Momentum?...it's that just the rate of my phase rotation under translations?
$$ e^{i\phi(x, t)} $$
with
$$ \phi(x, t) = i(kx-\omega t) $$
so that:
$$ p = -i\hbar\frac{\partial \phi}{\partial x} = \hbar k $$
Check. (I know it's not too intuitive, but it does yield $p=mv$ for a non-relativistic treatment.
I know that's an unsatisfying answer, but I think it is satisfactory.
But the real problem is: what are $E$ and $\vec p$? Well, they are components of a four vector:
$$ p_{\mu} = (E/c, \vec p) $$
For the arbitrary particle, that is:
$$ p_{\mu} = (\sqrt{(mc)^2 + p^2}, \vec p) $$
From there you would evaluate that in the rest frame to get:
$$ p_{\mu} = (mc, 0,0,0) $$
But for a massless particle there is no rest-frame. You have:
$$ p_{\mu} = (|\vec p|, \vec p) $$
in all frames. Now in our infinite stable (no GR) flat space-time, that can be any value we want, from infinity to arbitrarily close to zero (but not zero!), in any direction.
Let's say we start with 511 keV annihilation photon or a 21cm hydrogen line photon: their behaviors in our thought experiment are identical (up to polarization). Without a frame, the gamma ray or radio wave can be boosted to be anything we want them to be.
It is our Galilean sensibilities to say one is naturally higher energy than the other, but really, the origin of the photon is not relevant to the discussion.
Note also that for any relativistic particle, the ratio of energy to momentum is:
$$ \frac{E}{p} = \frac{\gamma mc^2}{\gamma m v} = c/\beta $$
so contrary to Newtonian intuition, mass means we need more energy to get a certain amount of momentum: counter intuitive. Of course, rest mass being equivalent to a lot of energy, since $c^2$ is huge, is not an intuitive result.
