As concept3d said, a pair of float4s means 8 components total (so half the size of a 16-component matrix), and you can just fit a rotation, translation, and uniform scale value into 8 components. (Although I would use a quaternion rather than axis-angle - that way no trig functions need to be used in the vertex shader to apply the rotation.)
As for the "Video memory overhead: model replication" comment, this is my best guess:
The context of the talk is trying to reduce the number of batches (draw calls) by combining multiple models together in a batch. You would ordinarily have to create a new batch every time you changed the world matrix, so the speaker envisions doing this with bones instead ("matrix palette" is an old hardware feature for making bone matrices available to the vertex shader). Basically you'd attach each model to a different bone and set each bone to the transform needed for that object.
However, this raises a problem where the object has to know which bone it should be attached to. This would be done by adding a new vertex component for the bone index. But this means you need a vertex buffer with multiple copies of the model, each with the bone index set to a different value in all its vertices. Therefore you are paying a lot of video memory overhead by replicating the model several times.
Nowadays we would do all of this with instancing, which solves that problem; but I don't think hardware instancing existed in 2003 or 2004 when this talk was given.