I understand that by convention, the cross product is defined to be the vertical projection of vector $A$ on $B$ in the case of $A \times B$. But the vertical projection of $A$ on $B$ would still be in the same coordinate-plane as $A$ and $B$. Why should the resultant cross-product necessarily point in the orthogonal direction given by the right hand rule? We have always taken it for granted when solving problems, and my textbook does not make any attempt at an explanation.
Why should the resultant cross-product necessarily point in the orthogonal direction given by the right hand rule?
Because, we made it to do so.
Other math tools/methods give other results. And we made them to do so too. We could make a mathematical method that brought any result we wanted. But some methods, tools and definitions turn out to fit with the real world.
Remember that math is a tool invented to describe phenomena among others. If we find some kind of a connection in the real world, we can design a mathematical tool to describe it.
You can sit down and invent any mathematical definition/tool of your own. Something with another value and another orientation after using it on two vectors. Something completely different, if you like. It is up to you. If it happens to be useful for anything, it might catch on and become a recognized mathematical rule.
Maybe in a few years, people will start asking, why this rule really is as it is. And your answer will simply be: Because it happens to describe something that we want to describe.
The question should not be, why the tool gives that resulting orientation. It should rather be, why those phenomena that fit that description work in that way.
The right hand rule and cross product of matrices is a convenient and useful tool for describing natural phenomena in three dimensional space. Like all conceptual tools, it was devised by humans to acquire knowledge, and to further our ability to predict and to manipulate aspects of our world. We use it because it fits with nature.
Examples ($\times$ denotes cross product):
The direction of magnetic force, electric current, and magnetic field derived from the Lorentz Force Law: $$F = q * (E + (v \times B))$$ where $F$ is the force felt by charge $q$ moving at velocity $v$ through an electric field E and a magnetic field $B$. (E, v and B are vectors.)
The direction of the magnetic field around a current carrying wire: $$F = L * I \times B$$ where $F$ is the force on the wire, $I$ is the electric current (assuming positive charges are flowing), $L$ is the length of the wire, and $B$ is the direction of the magnetic field.
The direction of the torque axis when force is applied to the axis: $$\tau = r \times F$$ where $\tau$ has the direction along the axis of rotation from which angular velocity of torque is applied, $r$ is the displacement vector along the lever arm through which torque is applied, and $F$ is the force vector applied at that distance.
The representation of a rotation vector (Euler vector), useful when describing any rigid object that rotates around an arbitrary axis.
The right hand rule works so well as an adjunct to matrix cross products in vector multiplication, that we might think nature follows math, rather than math following nature. The ancient Greek Pythagoreans believed as an article of faith that "all is number". But math is essentially no more than a language with tests for internal consistency and reality checking. We may get so drunk on the power of math that we turn it into something more real than the world to which we apply it, as the ancient Greek Pythagoreans did.
All language, beyond primitive simple words mimicking the sounds associated with natural phenomena, is arbitrary. Though its roots are in primal perceptions, language becomes arbitrary and abstract as humans expand the range of thought, and devise tools to extend their perceptions and power. (http://rstb.royalsocietypublishing.org/content/369/1651/20130299).
Math is no different. First came counting or "natural" numbers, then rational numbers, then irrational numbers, then zero, then negative numbers, then the square root of -1 and "imaginary" numbers, and then many more extensions of the concept of numbers (http://en.wikipedia.org/wiki/Number), including cross products of matrices and the right hand rule.