In effect, \"baking\" the vertices one time in software instead of per frame in hardware
Surely possible. Seems a bit a memory eater...

Sure its possible considering that 3d files are quite small
With vertex animation, they end up being quite big... you can easily have a few MB used by a specific body size character with animations.
Skeletal animation avoids this problem
in Phantasy star online you just kind of strecthed your own model to make it tall, short, fat or skinny
This is exactly what I mean with blend shapes: they are the technology used to have this kind of feature. They can be done in software (this is the way 3D softwares handled them till now), or in hardware, now that modern programmable cards allow vertex shaders.
make you do new animations for each and every model
Not necessarily: you must export different animations for different body sizes, but in the animation software you can still do only one animation valid for every case.
The problem is always the same, besides filesize: you can only have discretized body sizes (i.e. fat, normal, skinny), since you can\'t interpolate between them. The interpolation is done through blend shapes.