why is the vector cross product perpendicular to the plane of the two multiplied vectors?

It is merely a definition used by mathematicians and physicists.

a x b = moda. modb. sintheta. n(hat)

is the axiom someone invented many years ago which is useful for some problems.
More complications arise  when one realises that a x b is not really a true vector but a pseudo-vector but this does not worry a lot of people!

The right hand rule is a decent tool to use, but it does leave a little to be desired...

It's a matter of what the math below the term "cross-product" is.  The main reason we have a process such as taking the "cross-product" of two vectors in a plane is to find the vector (usually used to describe torque) that results.  So it's sort-of an intentional tool that we use.

I have a teacher that said several times that "the cross product is useful as a measure of "perpendicularness"?the magnitude of the cross product of any two vectors is equal to the product of their magnitudes if they are perpendicular.  But if they are parallel, it scales down to zero."

If you check out the math of taking the cross-product of two or more vectors it gets a little complicated, whether or not your doing it algebraically or with matrices.  The fact that absin(?) may be used in some cases is more of a shortcut and isn't the entire mathematical process.