OpenGl 2D sprites Z-Order -> Enableing depth test creates graphical error

Question

I am having trouble with the Z-ordering in OpenGL (only 2D).
I wrote a class which renders a list of sprite objects to the screen. The sprite objects have a distance property, which tells how far away from the camera they are.
As I read that binding a texture in openGL is slow, I tried to reduce the binding of textures to a minimum.
This is done by Having a map of >. So all sprite objects which use the same texture are saved in a list. When it comes to rendering, first the texture is binded and then all the objects with this texture are rendered. Then it binds the next texture and renders all objects for this etc.
Now the problem was: Although I use vertex3F to render the objects, they are not sorted correctly. Means: objects which should be far away are rendered over objects which should be as near as possible.
I could also solve this problem by enableing the depth test with the LEQUAL function. But now I have the following rendering error: This line of triangles starts at the upper left corner and goes all the screen to the lower right corner.

I have no idea where this error is coming from. Has someone an idea what causes this error and how it can be fixed?

Here is also the relevant code: Initializing:

GL11.glMatrixMode(GL11.GL_PROJECTION);
GL11.glLoadIdentity();
GL11.glOrtho(0, p_resolutionWidth, 0, p_resolutionHeight, 1, -1);
GL11.glMatrixMode(GL11.GL_MODELVIEW);

GL11.glClearDepth(1.0f); 
GL11.glEnable(GL11.GL_DEPTH_TEST); 
GL11.glDepthFunc(GL11.GL_LEQUAL);

GL11.glEnable(GL11.GL_BLEND);
GL11.glBlendFunc(GL11.GL_SRC_ALPHA, GL11.GL_ONE_MINUS_SRC_ALPHA);

Rendering all sprites:

GL11.glEnable(GL11.GL_TEXTURE_2D);
GL11.glPushMatrix();



for(Sprite sprite : m_sortedSprites.keySet()) {
    GL11.glBindTexture(GL11.GL_TEXTURE_2D, sprite.texture().getTextureID());

    GL11.glBegin(GL11.GL_QUADS);
    for(SpriteSceneObject spriteObject : m_sortedSprites.get(sprite)) {
        Rectangle rectangle = new Rectangle(spriteObject.position(), sprite.width(), sprite.height());

        if(p_camera.isVisible(rectangle)) {
            renderSprite(spriteObject, p_camera);
        }

    }
    GL11.glEnd();
}

SceneManager.setOpenGLColour(Colour.WHITE);

GL11.glPopMatrix();
GL11.glDisable(GL11.GL_TEXTURE_2D);

And rendering a single sprite:

private void renderSprite(SpriteSceneObject p_spriteObject, CameraSceneObject p_camera) {
    Sprite sprite = p_spriteObject.sprite();
    Rectangle rectangle = new Rectangle(p_spriteObject.position(), sprite.width(), sprite.height());
    Vector2 upperLeft = p_camera.worldToGraphicsCoordinate(rectangle.upperLeft());
    Vector2 upperRight = p_camera.worldToGraphicsCoordinate(rectangle.upperRight());
    Vector2 lowerRight = p_camera.worldToGraphicsCoordinate(rectangle.lowerRight());
    Vector2 lowerLeft = p_camera.worldToGraphicsCoordinate(rectangle.lowerLeft());

    Colour colour = p_spriteObject.colour();

    SceneManager.setOpenGLColour(colour);

    GL11.glTexCoord2f(0, 0); // Upper Left
    GL11.glVertex3f(upperLeft.x(), upperLeft.y(), p_spriteObject.distance().distance());

    GL11.glTexCoord2f(1, 0); // Upper Right
    GL11.glVertex3f(upperRight.x(), upperRight.y(), p_spriteObject.distance().distance());

    GL11.glTexCoord2f(1, 1); // Lower Right
    GL11.glVertex3f(lowerRight.x(), lowerRight.y(), p_spriteObject.distance().distance());

    GL11.glTexCoord2f(0, 1); // Lower Left
    GL11.glVertex3f(lowerLeft.x(), lowerLeft.y(), p_spriteObject.distance().distance());
}

I know that a possible fix would be to sort all sprites by their distance and then just render them. I also tried this and it works. But then it is not possible to pool sprites which use the same texture and therefore I have to bind every texture mor than once, which is unperformant.