I knew ahead of time that there were some issues with per vertex animation, aka vertex keys, but now I'm realizing I can't even rotate a regular cube. It will flatten or stretch on tweening. If you had a keyframe for every frame, making the mesh file almost 100s of times bigger, it still wouldn't work perfectly at high frame rates (I don't want to simply disable tweening.) Is this something game animations have had all along, or is there something I'm missing that prevents this problem? Lucky for me I use cal3d for all human meshes which doesn't have this problem, but I'm still wondering how it was dealt with...

You can rotate a cube perfectly fine using per-vertex animation. However, it is difficult and requires lots of storage (you need to store many keyframes). But vertex animation has obscene storage costs anyway (each keyframe is a complete duplicate of the mesh data), so what's a couple extra, right?

Vertex-key animation stopped being popular a long time ago. It is rarely used in modern game development, and when it is, it has very localized application (facial animation sometimes uses per-vertex animation still).

Most of the time, we use skeletal (bone/skin) animation nowadays.

Yeah, pre-canned vertex tweening is dead now that we have vertex shaders. Still occasionally useful is vertex blending; as jpetrie mentioned, it's useful for facial animation. It basically comes up in situations where it's difficult to rig a good skeletal structure but you still want complex animation.