I assume this is related to the speed of the bullet. That is, you're moving the bullet at some predefined speed and, to maintain said speed, the bullet needs to move some distance per each frame. Faster speeds require the bullet to move larger distances between frames.
Specifically, I'd guess that in the previous frame, the bullet has not yet collided. Now, it moves "X" pixels to maintain its speed. Now, in the next frame, it is colliding, but it's now visually inside the boundary of the target.
If your target is "thin" enough, this phenomenon can even cause a hit to not register at all since the bullet is on one side of the target in frameX and on the other side in frameX+1.
One possible fix would be to track the average distance the bullet moves between frames. Based on that, you could cast a ray (of that distance) ahead of the bullet. If that ray collides with your target, that basically means that you will hit the target in the next frame. Based on that you could start the "destroy stuff" workflow.