A good way to understand this is perhaps by means of knowing what the magnitude of the cross product means. If you have two vectors $v$ and $w$, then their cross product $v \times w$ is a vector orthogonal to the plane spanned by $v$ and $w$ and with the magnitude being the area of the paralelogram that has the vectors as sides.
Now, if you get just the vector $v$ and compute $v \times v$ the magnitude of this thing should be the area of the paralelogram with $v$ and $v$ as sides. However this paralelogram is degenerate (speaking loosely, there's no paralelogram at all in truth), so that it's area should really be zero.
If you consider on the other hand $v\times 0$ this would be in magnitude the area of the paralelogram whose sides are $v$ and $0$, however, again this paralelogram is degenerate and should have no area, so that $v\times 0 $ should be really the null vector.
Its not really an "intuition" thing, the cross product is defined that way. The following may help you understand why.
The short answer is that the cross product appears in many physical systems - most famously in calculating the force produced by an electrical current in a magnetic field. But this begs the question of why it appears so often in physics.
In physics, you often get linear relationships - in the example above doubling the current will double the force, as will doubling the magnetic field. So the current vector and magnetic vector are somehow multiplied together to find the force vector. You could potentially define vector multiplication in lots of ways. But there is an additional constraint in physics, that you must get the same answer for the force vector however you orient your co-ordinate system. Nature doesn't have a coordinate system, so the answer must be the same however you define what is the "x axis" and what is the "y axis". If you set up a coordinate system with the x axis along the direction of the magnetic field and the y axis along the current vector, then you should get the same answer for force as if you set up the co-ordinate system with x axis in the current direction and the y axis along the magnetic field direction.
All physical laws must follow this rule; nature doesn't have a preferred direction for x and y. The dot product (which presumably you have just learned about) follows this rule.
If you want to multiply two vectors in 3D space to form another vector, up to a constant term the only definition of vector multiplication which has this property of being independent of the coordinate system is the cross product. It is the unique definition of vector multiplication which is independent of the choice of coordinate system.
So nature follows this rule whenever two (3D) vectors are multiplied together to form a 3rd vector. Any other rule would be depend on the choice of coordinate system. So natural processes in three dimensions are in a sense forced to use this rule, because its the only rule which is independent of the co-ordinate system. In 2D, there is no possible rule which is independent of the co-ordinate system. In higher dimensions there are more choices. But we live in a 3D Universe (spatial dimensions), so the cross product rule is forced onto nature and hence onto physics and maths.
Best Answer
The determinant formula isn't so mysterious. Consider the cross product $\mathbf{v} = \langle a,b,c \rangle \times \langle d,e,f \rangle$ as the formal determinant
$$ \det \left(\begin{array}{ccc} \mathbf{i} & \mathbf{j} & \mathbf{k}\\ a & b & c \\ d & e & f \end{array} \right) $$
where $\mathbf{i}, \mathbf{j}, \mathbf{k}$ are the standard basis vectors. If instead one considers $\mathbf{i}, \mathbf{j}, \mathbf{k}$ as indeterminates and substitutes $x, y, z$ for them, this determinant computes the dot product $\mathbf{v} \cdot \langle x, y, z \rangle$. But letting $\langle x, y, z \rangle$ be $\langle a, b, c \rangle$ or $\langle d, e, f \rangle$ gives a zero determinant, so $\mathbf{v}$ is perpendicular to the latter two vectors, hence to the plane they span, as Omnomnomnom says.