Let $X = (1,1,0),(1,-1,0),(0,0,1)$ be the basis of unitary space $\mathbb{C}^3$. Let $A$ be a linear operator, and $\mathbb{A}$ it's matrix in basis $X$:
$$ \mathbb{A} = \begin{pmatrix}3 & i & 0\\ -i & 3 & 0\\ 0 & 0 & 4 \end{pmatrix} $$
Verify that $A$ is normal and find an orthonormal basis in which $A$ is diagonal.
On the first look, the operator is obviously hermitian, because it's matrix is hermitian. Hermitian operators are normal and thus orthogonally diagonalizable.
However, there's a theorem saying that $A$ is a normal operator if and only if it's matrix in some orthonormal basis is a normal matrix. In this case $X$ is not orthonormal basis, only orthogonal.
Is the observation of $A$ being hermitian incorrect then? I noticed that if I orthonormalize $X$ and transform $\mathbb{A}$ or transform $\mathbb{A}$ into standard basis (which is orthonormal under standard dot product) the hermitian property doesn't change.
Do I explicitly need to always convert to orthonormal basis to verify the normality, or are there some exceptions where the orthogonal is "sufficient"? What is the correct justification?
To avoid confusion, I will call your linear operator $T$ instead of $A$.
Let $D=\operatorname{diag}(\|x_1\|,\ldots,\|x_n\|)$. Then the orthonormal basis corresponding to the basis vectors in $X$ are given by the vectors in $XD^{-1}$. If the matrix of a linear operator $T$ w.r.t. the standard basis is $M$, then $\mathbb{A}=X^{-1}MX$ and the matrix of $T$ w.r.t. the (orthonormal) basis vectors in $XD$ is given by $(XD^{-1})^{-1}M(XD^{-1}) = D\mathbb{A}D^{-1}$.
Now the answer to your first question is both yes and no. No, in general, that $\mathbb{A}$ is normal (resp. Hermitian) does not necessarily imply that $D\mathbb{A}D^{-1}$ is also normal (resp. Hermitian). But yes, in your particular case, it happens that $D\mathbb{A}D^{-1}=\mathbb{A}$ (I'll leave the proof to you). So, the matrix of $T$ w.r.t. the orthonormal basis from $XD^{-1}$ is Hermitian. Therefore, $T$ is a normal operator.
At any rate, to show that $T$ is normal, you may prove that $M$ (the matrix of $T$ w.r.t the standard basis) or $D\mathbb{A}D^{-1}$ (the matrix of $T$ w.r.t. a orthonormal basis) is normal. In principle, showing that $\mathbb{A}$ is a normal matrix is irrelevant.