Why is it that the Z-buffer algorithm does not require polygons to be depth sorted to function correctly?
The Z-Buffer simply saves the Z value of each pixel as you draw them. That means that when you try to draw a new pixel, you compare its Z value with the one saved on the Z-Buffer.
That means that once the whole scene is drawn, and the game decided to draw one last polygon on the very far background, the value of the pixels on the Z-Buffer corresponding to that polygon will be higher than the Z value of the pixels belonging to the polygon, so they will not be drawn at all.
This guarantees that the scene will be rendered correctly, and no polygon will be drawn on top of another where it shouldn't. However the negative is the overdraw. Although there is no guarantee which polygon will be drawn first (depends on engine/framework used), there's a high chance a pixel on the screen will be drawn more than once.
As mentioned in the comments, for performance reasons, it's best to draw polygons from front to back, so that most polygons that are obscured won't be rendered at all.
Also an exception to this are semi-transparent polygons, which have to be Z-sorted and drawn after all opaque polygons are drawn.
For more information, see Z-buffering on Wikipedia