Everything that I've seen (including posts here and on Shawn Hargreaves' blog) and experienced points out that you can ONLY use SamplerState.AddressU = TextureAddressMode.Wrap when using SpriteSortMode.Immediate.
My game uses XNA to sort everything, so we're not using Immediate, and tiling it manually mostly works, but since these ...