I was wondering that if particles are indistinguishable in quantum mechanics ... Why don't we just talk about two particles, why do we have to give them labels, even if they don't affect measurement?
Let's recall what this indistinguishability means in practice: in order to get good agreement of calculations of atomic properties like emission line frequencies with experiments, Hamiltonian eigenfunctions are needed (they are not necessary but they make the calculation tractable). It turns out that ordinary atomic Hamiltonians have such properties (they are real and symmetric...) that their eigenfunctions are all either symmetric or antisymmetric with respect to exchange of two particles' coordinates.
It was found by comparison to measurements that for electrons, antisymmetric wave functions for electrons $\psi(\mathbf r_1, \mathbf r_2)$ should be used.
Now, where is indistinguishability in that? It lies in the fact that solely from an antisymmetric wave function $\psi(\mathbf r_1, \mathbf r_2)$, we cannot tell any difference in properties or behaviour of the particle 1 from the particle 2; the probability density that 1 is at A and 2 is at B is the same as the probability density that 2 is at A and 1 is at B.
It may come as a surprise, but it seems clear that to explain just what indistinguishability means in practice of atomic physics, we need at least two different entities, distinguishable in speech - and only then it can be said that we cannot distinguish them with the description based on the $\psi(\mathbf r_1, \mathbf r_2)$ function alone. It does not necessarily mean two or all electrons in the world are actually one and the same electron or anything metaphysical like that as people sometimes fantasize. Indistinguishability is just practical nuisance.
Why aren't $\left| \uparrow \downarrow \right\rangle$ and $\left| \downarrow \uparrow \right\rangle$ the same state?
These two kets refer to different states by definition; the position of the arrow within the ket matters and is intentionally chosen based on which one of the individual spin-carrying body is meant. We want the formalism to work this way because it allows us to easily describe situations like spin z up at the detector A (first position within the ket), spin down at detector B(second position within the ket). The behaviour you have in mind does happen, but with different ket - the symmetric ket
$$
\left|\uparrow\downarrow\right\rangle + \left|\downarrow \uparrow\right\rangle
$$
which can be written as $sym\{\uparrow,\downarrow\}$ or $sym\{\downarrow,\uparrow\}$; the order does not matter here.
Surely, if they are truly indistinguishable, labels are just a redundancy. Is there some mathematical reason behind this, or is there a deeper physical reason?
Distinct labels like $\mathbf r_1,\mathbf r_2$ are used for distinct particles partially because they were used already in classical mechanics, in particular in the Hamiltonian mechanics. Schroedinger devised his equation with this Hamiltonian formalism in mind, so it uses distinct coordinates as well. For example, we need them to formulate the Hamiltonian operator for the helium atom
$$
\hat{H} = - \frac{\hbar^2}{2m}\Delta_1 - \frac{\hbar^2}{2m}\Delta_2 + \frac{K}{4\pi}q_1 q_2 \frac{1}{|\mathbf r_1 - \mathbf r_2|} + \frac{K}{4\pi}Qq_1\frac{1}{|\mathbf r_1|} + \frac{K}{4\pi}Qq_2\frac{1}{|\mathbf r_2|}.
$$
There is no such thing as Schroedinger's equation with two indistinguishable variables. This should not be regarded as deficiency of his formalism - the variables are not particles after all. There is no difficulty with distinct variables referring to indistinguishable particles.
There is no indistinguishability in the formal objects - the two electrons are labeled by distinct variables. Only when seeking functions that solve the Schroedinger equation
$$
\hat{H} \Phi(\mathbf r_1, \mathbf r_2) = E \Phi(\mathbf r_1, \mathbf r_2)
$$
it turns out that these are all either symmetric or antisymmetric which means the description of the electron $1$ is the same as the description of the electron 2; one cannot tell anything different about the first second particle than about the second particle from the $\psi$ function alone.
If we want, we may even think that the two electrons are not exactly the same and are actually little bit different (for example, their mass may have variance $10^{-62}$kg, which is beyond our skills to measure). It should be clear that this does not prevent us to use anti-symmetric functions in calculations with advantage, nor to call electrons indistinguishable (when such mass differences are unmeasurable).