Why is the matrix-defined Cross Product of two 3D vectors always orthogonal?
Here's an explanation in terms of the Hodge dual and the exterior (wedge) product.
Let ${e_1, e_2, e_3}$ be the standard orthonormal basis for $\mathbb{R}^3$. Consider the two vectors $a = a_1 e_1 + a_2 e_2 + a_3 e_3$ and $b = b_1 e_1 + b_2 e_2 + b_3 e_3$. From the matrix computation we obtain the familiar formula
$a\times b = (a_2 b_3 - a_3 b_2) e_1 + (a_3 b_1 - a_1 b_3) e_2 + (a_1 b_2 - a_2 b_1) e_3$.
But (see note at the bottom)
$a \wedge b = (a_1 b_2 - a_2 b_1) e_1 \wedge e_2 + (a_2 b_3 - a_3 b_2) e_2 \wedge e_3 + (a_3 b_1 - a_1 b_3) e_3 \wedge e_1$,
where the wedge $\wedge$ represents the exterior product. One can now compute the dual of this latter expression using that the left contraction of $(e_1 \wedge e_2)$ onto $(e_3 \wedge e_2 \wedge e_1)$ is $e_3$ (and similar relations). The result is that
$a \times b = (a \wedge b)^*$,
that is, the cross product of $a$ and $b$ is the dual of their exterior product.
Geometrically, this is an incredible picture. The exterior product is the plane element spanned by both $a$ and $b$, and the dual is the vector orthogonal to that plane.
This is my favorite interpretation of the cross product, but it's only helpful, of course, if you're familiar with exterior algebra and the Hodge dual.
Note: The wedge product can be found by formally computing
$(a_1 e_1 + a_2 e_2 + a_3 e_3) \wedge (b_1 e_1 + b_2 e_2 + b_3 e_3)$
using the distributivity and anticommutation relations of the exterior product.
Assuming you know the definition of orthogonal as "a is orthogonal to b iff $a\cdot b=0$ then we could calculate $(a \times b)\cdot a = a_1(a_2b_3-a_3b_2)-a_2(a_1b_3-a_3b_1)-a_3(a_1b_2-a_2b_1)=0$ and $(a \times b)\cdot b-0$, so the cross product is orthogonal to both. As Nold mentioned, if the two vectors a and b lie in the x,y plane, then the orthogonal vectors must be purely in the z direction.
Note that if you replace $i$, $j$, and $k$ with $m$, $n$, and $p$, the determinant becomes the dot-product of the vector $(m, n, p)$ with the cross-product of the two original vectors. If $(m, n, p) = (a, b, c)$ or $(m, n, p) = (d, e, f)$, the determinant is zero (any matrix with two identical rows has determinant zero), so the dot product of $(a, b, c)$ or $(d, e, f)$ with the cross-product is zero. Hence, $(a, b, c)$ and $(d, e, f)$ are orthogonal to their cross-product.