Setting your min/mag/mip filters to Point should prevent the shader from interpolating the texels, which seems to be what your application calls for. Direct3D would default to that, but to make sure you can do this with:
texture MyTexture;
sampler MySampler =
sampler_state
{
Texture = <MyTexture>;
MinFilter = Point;
MagFilter = Point;
MipFilter = None;
};
More info on sampler states can be found over here.
That said, I don't know if the XNA SpriteBatch exactly aligns texels with screen pixels, but this has been a common pitfall in Direct3D development for ages. You can find more information about mapping texels to pixels on this MSDN page, maybe this is of some help.