But what is the quantum state of the electrons before the measurements? It seems to me that if it is anything but an eigenstate of Sz, then the perfect correlations are impossible.
Electrons have "wave particle duality" which sounds like philosophical garbage but is detectable in experiments such as this one. Rather than emitting the electrons in an unknown state, let's assume a device that specifically emits a pair of electrons that are 100% anti-correlated in Sx rather than Sz.
We will work in the usual Sz basis, and since Sx can be taken to be real in this basis, I'll ignore the difference between bra and ket vectors (and for convenience, write them all as bras). So one of the electrons is Sx+ = $(1,1)/\sqrt{2}$, the other is Sx- = $(1,-1)/\sqrt{2}$. The combined wave function is defined mathematically as a x product as in:
$$|x+-\rangle = (1,1)\times(1,-1)/2 = (1,1,-1,-1)/2.$$
But since electrons are indistinguishable, we could have the two electrons reversed. This would be the state:
$$|x-+\rangle = (1,-1)\times(1,1)/2 = (1,-1,1,-1)/2.$$
Note that the above two vectors are orthonormal.
Since electrons are fermions, we take the anti-symmetric combination. This means we take the difference between the above two joint wave functions:
$$|x+/-\rangle = (|x+-\rangle - |x-+\rangle)/\sqrt{2} = (0,1,-1,0)/\sqrt{2}.$$
Now let's redo the calculation with two electrons that have spin Sz anti-correlated so that Sz+ =$(1,0)$ and Sz- = $(0,1)$. The two possible cases are:
$$|z+-\rangle = (1,0)\times (0,1) = (0,0,1,0)$$
$$|z-+\rangle = (0,1)\times (1,0) = (0,1,0,0)$$
and the anti-symmetric combination is:
$$|z+/-\rangle = (|z+-\rangle - |z-+\rangle)/\sqrt{2} = (0,-1,1,0)/\sqrt{2}.$$
This is the same as we got for the x case $|x+/-\rangle$ (other than an overall factor of -1 which is just the usual arbitrary complex phase).
Thus we see that according to the rules for quantum mechanics, it doesn't matter which two electrons we begin with. They could be spin in the x direction or z direction, or any direction; you get the same joint wave function.
Now the above explanation may be unsatisfying in that it is mathematical. If you want a more physical explanation for what is going on, maybe the following will help.
You can think of the electrons as being excitations, that is, as waves. When you measure a wave, you alter the wave and change it. In the case of the anti-correlated electrons, the combined wave has just enough stuff to give you two electrons with opposite correlated spin. It doesn't matter which way the spins are arranged, there's just enough to give you a pair of them.
One must be careful when one talks about the passage of time in these experiments. The measurement typically takes place long after the electron wave function has been divided into two portions, say one going to one detector, the other to the other detector. It might be several nanoseconds before an apparatus is able to permanently record which electron had which spin. During THAT (i.e. measurement) time, the electron's wave function has to be changed into another form, one which is suitable for measurement. This cannot happen instantaneously and it does not happen AFTER the electron wave function is split. Until the measurement is made, the electron, along with the measuring apparatus, is all in a Schroedinger Cat sort of combined wave function. Either possible result is possible, but the electron wave function only has enough juice to do one of the two possibilities.
The same "explanation" applies to things like Wheeler's "delayed choice" experiment. There actually is no delay in the choice in that the combination of experiment and particle are in a combined wave state until the measurement becomes permanent.