Are projective measurement bases always orthonormal?

Are projective measurement bases always orthonormal?

Yes.

Remember that you require several properties of a projective measurement including $$P_i^2=P_i$$ for each projector, and $$\sum_iP_i=\mathbb{I}.$$ The first of these show you that the $$P_i$$ have eigenvalues 0 and 1. Now take a $$|\phi\rangle$$ that is an eigenvector of eigenvalue 1 of a particular projector $$P_i$$. Use this in the identity relation: $$\left(\sum_jP_j\right)|\phi\rangle=\mathbb{I}|\phi\rangle$$ Clearly, this simplifies to $$|\phi\rangle+\sum_{j\neq i}P_j|\phi\rangle=|\phi\rangle.$$ Hence, $$\sum_{j\neq i}P_j|\phi\rangle=0.$$ The $$P_j$$ are all non-negative, so the only way that this can be 0 is if $$P_j|\phi\rangle=0$$ for all $$j\neq i$$. (To expand upon this, assume there's a $$P_k$$ such that $$P_k|\phi\rangle=|\psi\rangle\neq 0$$. This means that $$\sum_{j\neq i,k}\langle\psi|P_j|\phi\rangle=-\langle\psi|P_k|\phi\rangle,$$ so some terms must be negative, which is impossible if the eigenvalues are all 0 and 1.)

Here is another way to see this.

A projection $$P$$ is an operator such that $$P^2=P$$.

This directly implies that we can attach to each projector $$P$$ a set of orthonormal states that represent it, by choosing any orthonormal base for its range. More precisely, if $$P_i$$ has trace $$\operatorname{tr}(P_i)=n$$, then we can represent $$P_i$$ as a set of orthonormal states $$\{\lvert\psi_{i,j}\rangle\}_{j=1}^n$$. Note in particular that if $$\operatorname{tr}(P_i)=1$$ then this choice is unique, meaning that there is always a bijection between trace-1 projections and states.

The projector $$P_i$$ and the corresponding states are connected through $$P_i=\sum_{j=1}^n \lvert\psi_{ij}\rangle\!\langle \psi_{ij}\rvert.$$ In the simpler case of $$\operatorname{tr}(P_i)=1$$ this reads $$P_i=\lvert\psi_i\rangle\!\langle\psi_i\rvert$$.

Now, if you are asking for a projective measurement basis, then you require a set of operators which describes every possible outcome of your state. This condition is expressed mathematically by requiring $$\sum_i P_i=I,$$ which in terms of the associated ket states reads $$\sum_{ij}\lvert\psi_{ij}\rangle\!\langle\psi_{ij}\rvert=I,$$ which is the completeness relation for the vectors $$\{\lvert\psi_{ij}\rangle\}_{ij}$$. This immediately implies that this is also an orthonormal set (to see it, take for example the sandwich of this expression with any $$\lvert\psi_{ij}\rangle$$).

Orthogonality of $$P_i$$ is equivalent to orthogonality of the corresponding $$\lvert\psi_{ij}\rangle$$, thus the conclusion.