I've looked over it again and I was talking nonsense. The FL_ONGROUND stuff doesn't apply in the way I said, and the test results I had earlier weren't valid.
I've also been looking at Quake 2's interpolation code. That's interesting because it handles both movement and frame interpolation together (and as a bonus rolls in the scale and scale_origin stuff). Looking at the handling of MOVETYPE_STEP, and the comments about it in the Quake 2 code, it's obvious that this is the way id originally intended it to work.
A quick and dirty port was able to successfully deal with origin interpolation but angles were still jerky as hell. All the same, it was promising enough that I think it's worth trying out in a vanilla Q1 codebase (just so as not to be polluted by any other changes made).
Different interpolation types for origin[0], origin[1] and origin[2] - tried it, didn't work.