OpenGL 2D Game Texture Artifacts

OpenGL 2D Game Texture Artifacts

I'm drawing supposedly a pixel-perfect game for iOS:
glitchypixels
The problem is that every few frames I see random pieces of another
texture being drawn (the teal dots floating in the blackness). First, I
tried making sure the quads all lined up completely. Next, I changed the
Z-buffer size. Neither of these things seemed to help.
I am using a texture atlas, but unfortunately I can't add in padding
pixels (one solution I've seen). Now, if I change the texture coordinates
from 0,1 to 0.005,0.95 the problem goes away but it looks like garbage.
Does the behavior of this screenshot suggest another solution I haven't
tied? Note that my filtering mode has to stay NEAREST for the sprite art,
and that the problem goes away when I force my character/camera to move in
whole pixel increments (which unfortunately doesn't feel as good as moving
in subpixels).