It turns out that the engine movement code for MOVETYPE_WALK doesn't seem to care about when you set origins. The bug cropped up for me when I tried to make a non-client respawn, and it kept on appearing either where it died, or at the same spawnpoint over and over again. Many hours later I realized it was linked to the entity's MOVETYPE_WALK. I was able to set origin fine when the entity was MOVETYPE_TOSS, but with WALK I couldn't even accurately set the origin, even when I set it a thousand or so times a second (the entity would spawn in the spot then begin to droop down below the location because of gravity, instead of constantly returning to that spot). So I'm guessing that some engine-side origin variable isn't getting set.
Thankfully I have come up with a hacky fix: set the entity's movetype to TOSS for 0.5 seconds when he respawns, then set it back to WALK afterwords. That way another movetype takes control long enough to get the offending variable reset before WALK takes over again.
However, please fix the bug soon. It's a rather ungainly fix, and MOVETYPE_WALK on non-players is going to be important in this mod.
