I'm using particle world in After Effects, with my own image as the "texture layer". But the image seems to "pop-in" at random while it is emitting. See the attached video.

It makes sense because it is 2.5D space and when the image moves forward in Z-space it just pops in front of another image. But it makes the whole effect unusable. I've tried every single setting such as explosive or cone axis etc... and it is a problem no matter what. Is there anyway to fix this?

As you say it's particles crossing in front of each other. There's probably something you can do that will spread them out a bit, but it will probably still happen.
I don't think it's really designed for low density particle systems. It's expecting to get a lot of help from fuzzy edges and transparency.

If you must use a big, hard edged thing like that, you might be able to thin out the emission a bit and then use several emitters/layers stacked in front of one another to get a similar effect (I can't recall if this is all that easy though, or possible for that matter)