Help please: Map of tiles has seams when a zoom is applied.

Im having quite a bit of trouble with zooming in on a map of tiles I am
drawing with DirectX (not DirectDraw). Drawing the actual tiles works
fine without a zoom:

But if I apply even a little bit of a zoom I get seems:

And this is driving me crazy.

I am using the Sprice to draw everything, and I am setting is transform
like so to do the zooming:
sprite.Transform = Matrix.RotationZ(0f) * Matrix.Scaling(viewZoom,
viewZoom, 1.0f) * Matrix.Translation(0f);

And it almost works! Which is what kills me, Im so close.

I have tried playing with the Device's RenderState and Texture stage to
a little avail: if I set
controller.Device.RenderState.SourceBlend = Blend.DestinationAlpha;

Then the problem completely goes away, but this turns off alpha
blending I think, such that textures that use alpha for transparancy
effects (overlayed on the base tiles) seem completely solid now.

I now *think* this problem may be something related to how I am loading
the texture. My texture is loaded from a png file, and I go through
and change three pixels colors to be transparaent right after its
loaded. I thought that was OK, but on a hunch I created a DDS texture
file with the alpha channel set up correctly and then the seams almost
disappeared. But not completely.

I am really not sure where else to go from here, other than maybe
trying to roll my own render method, or switching to DirectDraw which I
dont want to do. Anyone have help or ideas about where I should look?