I've got my new sprite batch system up and running, and I'm running into this weird depth testing issue where if I draw my sprite on top of another, it will clip the pixels of the underlying sprite as illustrated in the attached screenshot. Keep in mind that these two sprites are part of the same vertex buffer, and that the top sprite's are first in the vertex array. The top sprite also has a higher depth, and depth testing is on. Now, if I move the top sprite's vertices to the back of the vertex array, everything draws correctly. Is there a way I can get around this problem without having to rearrange my vertices from back-to-front?

I don't see any attached screenshots, but I'm guessing you just have an issue caused by transparency. If you want the end scene to look correct, you have to sort any polygons with transparency by depth and draw them after your non-transparent stuff. Blend(Blend(a,b),c) looks different than Blend(a,Blend(b,c)), and rendering a partially transparent sprite probably still updates the depth buffer meaning you can't draw anything behind the transparent portions of your sprite.

If that admittedly generic response doesn't cover you, seeing the screenshot would help know what's going on.

I think you've explained what's going on correctly, but I will re-upload the screenshot. I'm currently storing all of my vertices for my sprite batch in an STL vector. As nasty as this sounds, would it almost be better to just trash and rebuild my sprite's vertices from scratch whenever sprites change depths? For example, if 3 or 5 sprites change their depths in a frame, I could flag the vertex buffer to clear and refresh itself after all of the sprites have finished updating. This could be a huge performance problem though, and I would have to store a local copy of each sprite's vertices.

You can try rebuilding the sprite list every frame and stick with that until you hit performance problems. Also keep in mind you can use matrices to modify positions instead of directly updating vertex data. You can also use an index buffer to reorder the rendering. The render order is the only important part, not the actual storage.

In any case, this area probably shouldn't cause much ripple effects on the rest of your code base. That means you can probably delay optimization, and then you'll have more meaningful timing measurements to determine the right solution for your specific project. You also get to get back to working on the actual game instead of fighting with data structures.